square869120Contest #4

Submission #1294919

Source codeソースコード

/***********************************************
#
#      Filename: d.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-20 10:05:23
***********************************************/
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> a;
vector<double> dp;
vector<double> dp2;

double dfs(int cur, int par) {
    double ans = 0;
    int cnt = 0;
    for (auto v : a[cur]) {
        if (v != par) {
            ans += 1.0 + dfs(v, cur);
            ++ cnt;
        }
    }
    if (cnt) ans /= cnt;
    dp[cur] = ans;
    return ans;
}

void dfs2(int cur, int par, double back) {
//    cout << "cur: " << cur << " par: " << par << " back= " << back << endl;
    double ans = 0.0;
    for (auto v : a[cur]) {
        if (v == par) ans += back + 1.0;
        else ans += dp[v] + 1.0;
    }
    dp2[cur] = ans / a[cur].size();

    for (auto v : a[cur]) {
        if (v != par) {
            dfs2(v, cur, (ans - dp[v]-1) / max(1, (int)a[cur].size() - 1) );
        }
    }
}

int main()
{
    cin >> n;
    int u, v;
    a = vector<vector<int>> (n);
    dp = vector<double>(n);
    dp2 = vector<double>(n);
    for (int i = 0; i < n-1; ++ i) {
        cin >> u >> v;
        -- u; -- v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(0, -1);
    dfs2(0, -1, 0);
    
    for (int i = 0; i < n; ++ i)
        cout << fixed << setprecision(12) << dp2[i] << endl;
    return 0;
}

Submission

Task問題 D - Driving on a Tree
User nameユーザ名 comsyl
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1527 Byte
File nameファイル名
Exec time実行時間 505 ms
Memory usageメモリ使用量 18816 KB

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 190 / 190 sub1_in1.txt,sub1_in2.txt,sub1_in3.txt
Subtask2 220 / 220 sub2_in1.txt,sub2_in2.txt
Subtask3 390 / 390 sub1_in1.txt,sub1_in2.txt,sub1_in3.txt,sub2_in1.txt,sub2_in2.txt,sub3_in1.txt,sub3_in2.txt,sub3_in3.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sub1_in1.txt AC 2 ms 256 KB
sub1_in2.txt AC 5 ms 384 KB
sub1_in3.txt AC 376 ms 14976 KB
sub2_in1.txt AC 4 ms 384 KB
sub2_in2.txt AC 4 ms 384 KB
sub3_in1.txt AC 505 ms 13056 KB
sub3_in2.txt AC 443 ms 13556 KB
sub3_in3.txt AC 489 ms 18816 KB