ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 19.02.2019 18:12:24

ამოცანა: სამეფო სამკაული

მომხმარებელი: xXG2GiXx

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
#define fo(i,n) for(i=0; i<n; i++)
#define pb push_back
struct st{
  int x,y;
};
vector <int> v[5005];
int a[5005],b[5005],n,m;
st c[5005];
bool vis[5005];

int dfs1(int x){
    int i,p=a[x];
    vis[x]=1;
    fo(i,v[x].size()){
         if (!vis[v[x][i]]) p+=dfs1(v[x][i]);
    }
    b[x]=p;
    return p;
}

void dfs2(int x){
     int i;
     vis[x]=1;
     c[x].x=m;
     fo(i,v[x].size()){
          if (!vis[v[x][i]]) m++, dfs2(v[x][i]);
     }
     c[x].y=m;
     return;
}

int i,j,minn,l,r;

int main()
{
 	//freopen("royal.in" , "r" , stdin);
	//freopen("royal.out" , "w" , stdout);

      scanf("%d",&n);
      fo(i,n) scanf("%d",&a[i]);
      fo(i,n-1){
          scanf("%d%d",&l,&r); l--; r--;
          v[l].pb(r); v[r].pb(l);
      }
      
      l=dfs1(0);
      memset(vis,0,sizeof(vis));
      m=1;
      dfs2(0);
      
      minn=100000000;
      
      fo(i,n){
         for(j=i+1; j<n; j++){
             if (c[i].x>c[j].x && c[i].y<=c[j].y){
                 minn=min(minn,max(max(b[j]-b[i],b[i]),max(b[0]-b[j],b[i])));
             } else
             if (c[j].x>c[i].x && c[j].y<=c[i].y){
                 minn=min(minn,max(max(b[i]-b[j],b[j]),max(b[0]-b[i],b[j])));
             } else
             {
                 minn=min(minn,max(max(b[i],b[j]),max(b[i],b[0]-b[i]-b[j])));
             }
         }
      }
      
      cout<<minn<<endl;
      return 0;  
}

ტესტები

შემავალი მონაცემები
6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4
გამომავალი მონაცემები
70
თქვენი პასუხი
70
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10
313
178
121
334
376
442
27
177
460
322
1 2
2 3
3 4
4 5
4 6
5 7
6 8
8 9
9 10
გამომავალი მონაცემები
1179
თქვენი პასუხი
1179
ჩეკერის პასუხი
YES
შემავალი მონაცემები
20
139
97
54
158
457
210
142
336
464
273
301
88
63
487
152
469
207
177
439
26
1 2
2 3
2 4
3 5
4 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
14 16
15 17
16 18
18 19
19 20
გამომავალი მონაცემები
1957
თქვენი პასუხი
1957
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
404
162
162
112
217
201
316
87
453
130
150
426
324
454
422
148
442
95
68
386
413
412
240
129
100
447
200
64
295
223
456
174
199
393
135
392
429
275
346
277
133
204
153
285
227
47
106
289
99
84
219
192...
გამომავალი მონაცემები
10651
თქვენი პასუხი
10651
ჩეკერის პასუხი
YES
შემავალი მონაცემები
300
349
381
356
20
150
47
169
461
434
370
92
403
479
331
308
377
55
73
275
417
91
257
60
132
396
422
131
236
264
122
469
114
51
455
22
110
393
97
238
380
202
287
89
489
493
63
7
4
183
211
251
463
237
81...
გამომავალი მონაცემები
36711
თქვენი პასუხი
36711
ჩეკერის პასუხი
YES
შემავალი მონაცემები
800
342
252
37
292
301
295
319
121
415
253
422
75
151
116
217
111
153
144
72
345
113
131
482
222
35
152
173
183
434
415
236
466
298
276
132
323
484
468
477
10
303
288
275
275
359
148
279
373
292
125
193
4...
გამომავალი მონაცემები
142197
თქვენი პასუხი
142197
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1400
232
491
311
285
151
148
314
308
126
392
192
174
129
8
447
346
488
176
133
491
33
385
333
66
493
150
22
48
118
28
457
464
345
362
251
161
479
305
308
302
499
374
124
72
116
124
288
23
189
354
141
177
...
გამომავალი მონაცემები
179249
თქვენი პასუხი
179249
ჩეკერის პასუხი
YES
შემავალი მონაცემები
2500
210
404
125
7
416
155
135
146
480
303
363
475
19
122
41
119
263
372
57
152
174
93
35
187
345
80
483
446
286
186
334
262
138
6
291
402
168
280
337
218
128
84
57
99
459
10
372
57
20
247
103
14
307
22...
გამომავალი მონაცემები
390926
თქვენი პასუხი
390926
ჩეკერის პასუხი
YES
შემავალი მონაცემები
4000
14
209
372
118
29
405
240
21
225
233
216
130
272
39
327
373
276
66
55
418
355
396
229
305
321
291
156
211
191
251
333
391
300
144
154
361
102
422
270
494
8
124
471
232
225
45
406
16
140
25
431
242
1...
გამომავალი მონაცემები
452827
თქვენი პასუხი
452827
ჩეკერის პასუხი
YES
შემავალი მონაცემები
5000
323
478
412
276
141
97
445
154
198
131
495
479
101
268
50
6
452
2
85
147
148
59
269
162
473
468
477
328
303
32
361
377
321
446
120
194
69
129
215
247
491
50
114
423
142
308
129
495
178
167
341
105
1...
გამომავალი მონაცემები
581038
თქვენი პასუხი
581038
ჩეკერის პასუხი
YES