Submission #1292356
Source Code Expand
#include<cstdio> #include<vector> using namespace std; using ll=long long; using vi=vector<int>; using vvi=vector<vi>; using edge_t=pair<int,double>; using vve=vector<vector<edge_t> >; vve v; double solve_r(int cur, int prev) { double ret; int n; n=v[cur].size(); if(prev>=0) n--; if(n==0) { return 0.0; } ret=0.0; for(auto& e: v[cur]) { if(e.first==prev) continue; if(e.second<0) { e.second=solve_r(e.first, cur); } ret+=e.second+1; } return ret/n; } void solve(vector<double>& r) { for(int i=1;i<v.size();i++) { r[i]=solve_r(i, -1); } } int main(void) { vector<double> r; int n, a, b; while(scanf("%d", &n)==1) { v.clear(); v.resize(n+1); r.resize(n+1); for(int i=0;i<n-1;i++) { scanf("%d%d", &a, &b); v[a].push_back(make_pair(b, -1.0)); v[b].push_back(make_pair(a, -1.0)); } solve(r); for(int i=1;i<=n;i++) { printf("%f\n", r[i]); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Driving on a Tree |
User | myanta |
Language | C++14 (GCC 5.4.1) |
Score | 410 |
Code Size | 1011 Byte |
Status | TLE |
Exec Time | 1056 ms |
Memory | 20352 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:65:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 190 / 190 | 220 / 220 | 0 / 390 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | sub1_in1.txt, sub1_in2.txt, sub1_in3.txt |
Subtask2 | sub2_in1.txt, sub2_in2.txt |
Subtask3 | sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sub1_in1.txt | AC | 1 ms | 256 KB |
sub1_in2.txt | AC | 2 ms | 384 KB |
sub1_in3.txt | AC | 113 ms | 15616 KB |
sub2_in1.txt | AC | 2 ms | 384 KB |
sub2_in2.txt | AC | 2 ms | 384 KB |
sub3_in1.txt | AC | 109 ms | 13824 KB |
sub3_in2.txt | TLE | 1056 ms | 14832 KB |
sub3_in3.txt | AC | 89 ms | 20352 KB |