Submission #1986049
Source Code Expand
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define ele int using namespace std; #define maxn 200010 const ele INF=1e9; struct edge{ ele v; edge *nxt; }ep[maxn<<1],*ecnt; ele n,d[maxn],f[maxn]; edge *h[maxn]; inline void addedge(ele u,ele v){ edge *p=ecnt++; p->v=v; p->nxt=h[u]; h[u]=p; } void dfs(ele p,ele i,ele B){ vector<ele> lst; for (edge *j=h[i]; j; j=j->nxt) if (j->v!=p){ dfs(i,j->v,B); lst.push_back(f[j->v]); } if (lst.size()%2==0) lst.push_back(0); sort(lst.begin(),lst.end()); f[i]=INF; for (int r=0; r<lst.size(); ++r){ ele u=0,v=lst.size()-1; bool flag=true; while (u<v){ if (u==r) ++u; if (v==r) --v; if (u<v && lst[u]+lst[v]>B){ flag=false; break; } ++u; --v; } if (flag){ f[i]=lst[r]+1; break; } } } inline bool test(ele B){ dfs(-1,0,B); return f[0]<=B+1; } int main(){ scanf("%d",&n); ecnt=ep; memset(h,0,sizeof(h)); memset(d,0,sizeof(d)); for (int i=0; i<n-1; ++i){ ele x,y; scanf("%d%d",&x,&y); --x,--y; addedge(x,y); addedge(y,x); ++d[x]; ++d[y]; } ele cnt=0; for (int i=0; i<n; ++i) if (d[i]&1) ++cnt; ele L=0,R=n-1; while (R-L>1){ ele mid=(L+R)>>1; if (test(mid)) R=mid; else L=mid; } printf("%d %d\n",cnt/2,R); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Christmas Tree |
User | eleele |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1315 Byte |
Status | WA |
Exec Time | 218 ms |
Memory | 16256 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:47:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&x,&y); --x,--y; ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 900 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 197 ms | 8320 KB |
02.txt | AC | 207 ms | 8320 KB |
03.txt | AC | 206 ms | 8320 KB |
04.txt | AC | 206 ms | 8320 KB |
05.txt | WA | 176 ms | 15104 KB |
06.txt | WA | 174 ms | 16256 KB |
07.txt | AC | 211 ms | 11008 KB |
08.txt | AC | 212 ms | 12800 KB |
09.txt | AC | 216 ms | 11520 KB |
10.txt | AC | 201 ms | 13184 KB |
11.txt | AC | 138 ms | 8620 KB |
12.txt | AC | 138 ms | 8612 KB |
13.txt | AC | 138 ms | 8624 KB |
14.txt | AC | 138 ms | 8576 KB |
15.txt | AC | 205 ms | 8320 KB |
16.txt | AC | 208 ms | 8320 KB |
17.txt | AC | 195 ms | 8320 KB |
18.txt | AC | 179 ms | 8448 KB |
19.txt | AC | 161 ms | 8448 KB |
20.txt | AC | 162 ms | 8448 KB |
21.txt | AC | 163 ms | 8576 KB |
22.txt | AC | 164 ms | 9216 KB |
23.txt | WA | 176 ms | 14976 KB |
24.txt | AC | 166 ms | 14464 KB |
25.txt | AC | 205 ms | 8320 KB |
26.txt | AC | 197 ms | 8320 KB |
27.txt | AC | 196 ms | 8320 KB |
28.txt | AC | 180 ms | 8320 KB |
29.txt | AC | 170 ms | 8448 KB |
30.txt | AC | 170 ms | 8448 KB |
31.txt | AC | 171 ms | 8704 KB |
32.txt | AC | 172 ms | 9472 KB |
33.txt | WA | 165 ms | 14848 KB |
34.txt | WA | 174 ms | 13824 KB |
35.txt | AC | 218 ms | 8320 KB |
36.txt | AC | 216 ms | 8320 KB |
37.txt | AC | 209 ms | 8320 KB |
38.txt | AC | 192 ms | 8320 KB |
39.txt | AC | 167 ms | 8448 KB |
40.txt | AC | 161 ms | 8448 KB |
41.txt | AC | 172 ms | 8576 KB |
42.txt | AC | 175 ms | 9600 KB |
43.txt | WA | 165 ms | 12160 KB |
44.txt | WA | 168 ms | 11904 KB |
45.txt | AC | 206 ms | 8320 KB |
46.txt | AC | 193 ms | 8320 KB |
47.txt | AC | 209 ms | 8320 KB |
48.txt | AC | 192 ms | 8320 KB |
49.txt | AC | 167 ms | 8448 KB |
50.txt | AC | 173 ms | 8448 KB |
51.txt | AC | 171 ms | 8704 KB |
52.txt | AC | 164 ms | 9088 KB |
53.txt | AC | 173 ms | 11136 KB |
54.txt | AC | 174 ms | 13312 KB |
55.txt | AC | 131 ms | 9292 KB |
56.txt | AC | 131 ms | 9292 KB |
57.txt | AC | 131 ms | 9292 KB |
58.txt | AC | 131 ms | 9292 KB |
59.txt | AC | 196 ms | 11008 KB |
60.txt | AC | 197 ms | 10368 KB |
61.txt | AC | 196 ms | 10624 KB |
62.txt | AC | 196 ms | 11008 KB |
63.txt | AC | 196 ms | 11520 KB |
64.txt | WA | 154 ms | 12704 KB |
65.txt | AC | 148 ms | 12288 KB |
66.txt | WA | 161 ms | 11992 KB |
67.txt | AC | 2 ms | 3840 KB |
68.txt | AC | 2 ms | 3840 KB |
69.txt | AC | 2 ms | 3840 KB |
70.txt | AC | 2 ms | 3840 KB |
71.txt | AC | 2 ms | 3840 KB |
72.txt | AC | 2 ms | 3840 KB |
s1.txt | AC | 2 ms | 3840 KB |
s2.txt | AC | 2 ms | 3840 KB |
s3.txt | AC | 2 ms | 3840 KB |