oj.uz

Submission #348896

# Submission time Handle Problem Language Result Execution time Memory
348896 2021-01-16T04:53:49 Z juggernaut Highway Tolls (IOI18_highway) C++14
90 / 100
 850 ms 10440 KB 
#include"highway.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
vector<pair<int,int>>g[90005];
int h[90005],p[90005];
int n,m;
long long pivot;
int depth(int root){
    for(int i=0;i<n;i++)h[i]=0,p[i]=i;
    queue<int>q;
    int timer=0;
    q.push(root);
    h[root]=1;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(auto to:g[v])if(!h[to.first]){
            q.push(to.first);
            h[to.first]=h[v]+1;
        }
    }
    sort(p,p+n,[](int x,int y){return h[x]>h[y];});
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)>>1;
        vector<int>v(m,0);
        for(int i=0;i<=mid;i++)
            for(auto to:g[p[i]])v[to.second]=1;
        if(ask(v)==pivot)l=mid+1;
        else r=mid;
    }
    return p[l];
}
void find_pair(int n,vector<int>x,vector<int>y,int a,int b){
    ::n=n;::m=x.size();
    pivot=ask(vector<int>(m,0));
    for(int i=0;i<m;i++){
        g[x[i]].push_back({y[i],i});
        g[y[i]].push_back({x[i],i});
    }
    int s=depth(depth(0));
    int t=depth(s);
    answer(s,t);
}
/*
5 4 1 2 0 4
0 1
0 2
1 3
1 4
*/

Compilation message

highway.cpp: In function 'int depth(int)':
highway.cpp:14:9: warning: unused variable 'timer' [-Wunused-variable]
   14 |     int timer=0;
      |         ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 2 ms 2412 KB Output is correct
3 Correct 2 ms 2412 KB Output is correct
4 Correct 2 ms 2412 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2412 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 2 ms 2412 KB Output is correct
9 Correct 2 ms 2432 KB Output is correct
10 Correct 2 ms 2424 KB Output is correct
11 Correct 2 ms 2412 KB Output is correct
12 Correct 2 ms 2412 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2540 KB Output is correct
2 Correct 28 ms 3052 KB Output is correct
3 Correct 485 ms 8632 KB Output is correct
4 Correct 375 ms 8560 KB Output is correct
5 Correct 401 ms 8480 KB Output is correct
6 Correct 257 ms 8528 KB Output is correct
7 Correct 567 ms 8524 KB Output is correct
8 Correct 578 ms 8496 KB Output is correct
9 Correct 508 ms 8424 KB Output is correct
10 Correct 365 ms 8432 KB Output is correct
11 Correct 579 ms 8008 KB Output is correct
12 Correct 506 ms 7824 KB Output is correct
13 Correct 580 ms 7792 KB Output is correct
14 Correct 352 ms 7796 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3052 KB Output is correct
2 Correct 36 ms 3668 KB Output is correct
3 Correct 52 ms 4284 KB Output is correct
4 Correct 170 ms 8072 KB Output is correct
5 Correct 181 ms 7792 KB Output is correct
6 Correct 141 ms 7880 KB Output is correct
7 Correct 141 ms 7788 KB Output is correct
8 Correct 157 ms 7908 KB Output is correct
9 Correct 156 ms 7912 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2540 KB Output is correct
2 Correct 27 ms 3052 KB Output is correct
3 Correct 376 ms 7112 KB Output is correct
4 Correct 541 ms 8484 KB Output is correct
5 Correct 510 ms 8492 KB Output is correct
6 Correct 565 ms 8492 KB Output is correct
7 Correct 525 ms 8392 KB Output is correct
8 Correct 575 ms 8448 KB Output is correct
9 Correct 349 ms 8380 KB Output is correct
10 Correct 511 ms 8476 KB Output is correct
11 Correct 476 ms 7976 KB Output is correct
12 Correct 311 ms 7792 KB Output is correct
13 Correct 385 ms 7792 KB Output is correct
14 Correct 487 ms 7856 KB Output is correct
15 Correct 561 ms 8392 KB Output is correct
16 Correct 515 ms 8484 KB Output is correct
17 Correct 380 ms 7912 KB Output is correct
18 Correct 519 ms 7788 KB Output is correct
19 Correct 597 ms 8396 KB Output is correct
20 Correct 553 ms 7864 KB Output is correct
21 Correct 318 ms 8960 KB Output is correct
22 Correct 246 ms 9056 KB Output is correct
23 Correct 272 ms 8800 KB Output is correct
24 Correct 186 ms 8604 KB Output is correct
25 Correct 231 ms 7896 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3180 KB Output is correct
2 Correct 27 ms 3300 KB Output is correct
3 Correct 427 ms 8936 KB Output is correct
4 Correct 424 ms 9260 KB Output is correct
5 Correct 562 ms 10344 KB Output is correct
6 Correct 466 ms 10264 KB Output is correct
7 Correct 514 ms 10296 KB Output is correct
8 Correct 353 ms 10272 KB Output is correct
9 Correct 217 ms 8400 KB Output is correct
10 Correct 227 ms 9040 KB Output is correct
11 Correct 304 ms 9144 KB Output is correct
12 Correct 498 ms 9924 KB Output is correct
13 Correct 464 ms 10084 KB Output is correct
14 Correct 477 ms 10284 KB Output is correct
15 Correct 432 ms 10312 KB Output is correct
16 Correct 402 ms 9360 KB Output is correct
17 Correct 271 ms 9024 KB Output is correct
18 Correct 204 ms 9220 KB Output is correct
19 Correct 204 ms 9028 KB Output is correct
20 Correct 228 ms 9172 KB Output is correct
21 Correct 850 ms 10244 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3180 KB Output is correct
2 Correct 22 ms 3180 KB Output is correct
3 Partially correct 540 ms 8872 KB Output is partially correct
4 Partially correct 466 ms 9108 KB Output is partially correct
5 Correct 328 ms 9376 KB Output is correct
6 Partially correct 517 ms 10248 KB Output is partially correct
7 Correct 360 ms 8904 KB Output is correct
8 Partially correct 559 ms 9092 KB Output is partially correct
9 Correct 529 ms 9400 KB Output is correct
10 Partially correct 524 ms 10292 KB Output is partially correct
11 Correct 579 ms 10284 KB Output is correct
12 Partially correct 506 ms 10356 KB Output is partially correct
13 Correct 250 ms 9180 KB Output is correct
14 Correct 219 ms 8936 KB Output is correct
15 Correct 384 ms 9276 KB Output is correct
16 Correct 256 ms 8976 KB Output is correct
17 Correct 266 ms 9188 KB Output is correct
18 Correct 214 ms 9028 KB Output is correct
19 Correct 424 ms 9892 KB Output is correct
20 Correct 544 ms 10220 KB Output is correct
21 Partially correct 634 ms 10264 KB Output is partially correct
22 Partially correct 381 ms 10292 KB Output is partially correct
23 Correct 311 ms 10256 KB Output is correct
24 Partially correct 468 ms 10244 KB Output is partially correct
25 Partially correct 649 ms 10440 KB Output is partially correct
26 Partially correct 695 ms 10320 KB Output is partially correct
27 Partially correct 335 ms 9104 KB Output is partially correct
28 Partially correct 240 ms 9056 KB Output is partially correct
29 Partially correct 295 ms 9316 KB Output is partially correct
30 Correct 287 ms 9152 KB Output is correct
31 Correct 335 ms 9012 KB Output is correct
32 Partially correct 250 ms 8936 KB Output is partially correct
33 Correct 327 ms 9208 KB Output is correct
34 Partially correct 292 ms 9208 KB Output is partially correct
35 Correct 290 ms 9116 KB Output is correct
36 Partially correct 199 ms 8900 KB Output is partially correct
37 Partially correct 231 ms 9172 KB Output is partially correct
38 Correct 252 ms 9160 KB Output is correct
39 Partially correct 742 ms 10308 KB Output is partially correct
40 Partially correct 749 ms 10360 KB Output is partially correct
41 Partially correct 319 ms 10152 KB Output is partially correct
42 Partially correct 702 ms 10392 KB Output is partially correct