square869120Contest #4

Submission #1294885

Source codeソースコード

#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;

vector<int> G[1<<18];
double dp [1<<18];
double dp2 [1<<18];

double dfs(int u,int p) {
    int cnt = 0;
    double ans = 0;
    for(int i = 0; i < G[u].size(); i ++) {
        if (G[u][i] == p) continue;
        ans += dfs(G[u][i], u) + 1;
        cnt ++;
    }
    return dp[u] = cnt ? ans / cnt : 1;
}

void dfs2(int u, int p, double a) {
    double ans=0;
    for(int i=0;i<G[u].size();i++)
    {
        if(G[u][i]==p)ans+=a;
        else ans+=dp[G[u][i]];
    }
    dp2[u] = ans/G[u].size();
    for(int i=0;i<G[u].size();i++)
    {
        if(G[u][i]==p)continue;
        dfs2(G[u][i],u, 1+(ans-dp[G[u][i]])/max(1,(int)G[u].size()-1));
    }
}

int main()
{
    int n;
    cin>>n;
    int u,v;
    for(int i = 1; i < n; i ++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0, 0);
    for(int i = 1; i <= n; i ++) {
        cout << 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状態 WA
Score得点 190
Source lengthソースコード長 1090 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 190 / 190 sub1_in1.txt,sub1_in2.txt,sub1_in3.txt
Subtask2 0 / 220 sub2_in1.txt,sub2_in2.txt
Subtask3 0 / 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 4 ms 8448 KB
sub1_in2.txt AC 7 ms 8576 KB
sub1_in3.txt AC 373 ms 18944 KB
sub2_in1.txt WA
sub2_in2.txt WA
sub3_in1.txt WA
sub3_in2.txt AC 434 ms 15220 KB
sub3_in3.txt WA