oj.uz

Submission #348924

# Submission time Handle Problem Language Result Execution time Memory
348924 2021-01-16T05:53:46 Z juggernaut Highway Tolls (IOI18_highway) C++14
90 / 100
 758 ms 37628 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;
map<vector<int>,long long>mp;
long long o_ask(vector<int>v){
    if(mp.count(v))return mp[v];
    else return mp[v]=ask(v);
}
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(o_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=o_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(n-1));
    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:19:9: warning: unused variable 'timer' [-Wunused-variable]
   19 |     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 3 ms 2412 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 2 ms 2412 KB Output is correct
7 Correct 3 ms 2500 KB Output is correct
8 Correct 2 ms 2500 KB Output is correct
9 Correct 3 ms 2412 KB Output is correct
10 Correct 2 ms 2412 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 4 ms 2668 KB Output is correct
2 Correct 29 ms 4844 KB Output is correct
3 Correct 453 ms 26668 KB Output is correct
4 Correct 338 ms 26648 KB Output is correct
5 Correct 469 ms 26664 KB Output is correct
6 Correct 257 ms 21072 KB Output is correct
7 Correct 491 ms 26576 KB Output is correct
8 Correct 549 ms 27236 KB Output is correct
9 Correct 467 ms 26396 KB Output is correct
10 Correct 309 ms 26624 KB Output is correct
11 Correct 546 ms 25708 KB Output is correct
12 Correct 493 ms 20188 KB Output is correct
13 Correct 572 ms 26196 KB Output is correct
14 Correct 510 ms 19720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4588 KB Output is correct
2 Correct 37 ms 7096 KB Output is correct
3 Correct 75 ms 9296 KB Output is correct
4 Correct 218 ms 26080 KB Output is correct
5 Correct 228 ms 26184 KB Output is correct
6 Correct 163 ms 19728 KB Output is correct
7 Correct 264 ms 23644 KB Output is correct
8 Correct 182 ms 20884 KB Output is correct
9 Correct 254 ms 25412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2668 KB Output is correct
2 Correct 28 ms 4716 KB Output is correct
3 Correct 465 ms 20264 KB Output is correct
4 Correct 612 ms 26856 KB Output is correct
5 Correct 581 ms 25672 KB Output is correct
6 Correct 607 ms 26688 KB Output is correct
7 Correct 532 ms 23872 KB Output is correct
8 Correct 634 ms 25368 KB Output is correct
9 Correct 322 ms 26604 KB Output is correct
10 Correct 559 ms 26344 KB Output is correct
11 Correct 437 ms 26040 KB Output is correct
12 Correct 302 ms 26080 KB Output is correct
13 Correct 436 ms 25716 KB Output is correct
14 Correct 546 ms 26072 KB Output is correct
15 Correct 703 ms 26060 KB Output is correct
16 Correct 451 ms 23868 KB Output is correct
17 Correct 437 ms 24032 KB Output is correct
18 Correct 538 ms 25696 KB Output is correct
19 Correct 584 ms 24864 KB Output is correct
20 Correct 565 ms 26048 KB Output is correct
21 Correct 352 ms 27164 KB Output is correct
22 Correct 266 ms 27148 KB Output is correct
23 Correct 317 ms 22004 KB Output is correct
24 Correct 219 ms 27244 KB Output is correct
25 Correct 267 ms 25760 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5116 KB Output is correct
2 Correct 30 ms 5228 KB Output is correct
3 Correct 471 ms 29424 KB Output is correct
4 Correct 388 ms 31604 KB Output is correct
5 Correct 455 ms 36556 KB Output is correct
6 Correct 451 ms 37628 KB Output is correct
7 Correct 577 ms 36640 KB Output is correct
8 Correct 365 ms 36032 KB Output is correct
9 Correct 263 ms 31672 KB Output is correct
10 Correct 284 ms 33316 KB Output is correct
11 Correct 301 ms 32520 KB Output is correct
12 Correct 442 ms 35876 KB Output is correct
13 Correct 491 ms 36452 KB Output is correct
14 Correct 496 ms 36588 KB Output is correct
15 Correct 512 ms 36204 KB Output is correct
16 Correct 360 ms 34624 KB Output is correct
17 Correct 334 ms 27836 KB Output is correct
18 Correct 224 ms 27448 KB Output is correct
19 Correct 261 ms 27668 KB Output is correct
20 Correct 279 ms 21976 KB Output is correct
21 Correct 688 ms 36680 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5056 KB Output is correct
2 Correct 20 ms 5140 KB Output is correct
3 Partially correct 628 ms 29400 KB Output is partially correct
4 Partially correct 554 ms 30684 KB Output is partially correct
5 Partially correct 342 ms 32020 KB Output is partially correct
6 Partially correct 438 ms 37052 KB Output is partially correct
7 Correct 585 ms 28464 KB Output is correct
8 Partially correct 567 ms 30668 KB Output is partially correct
9 Correct 610 ms 31568 KB Output is correct
10 Partially correct 508 ms 36608 KB Output is partially correct
11 Correct 369 ms 36616 KB Output is correct
12 Correct 546 ms 36544 KB Output is correct
13 Correct 341 ms 34472 KB Output is correct
14 Correct 254 ms 32264 KB Output is correct
15 Correct 399 ms 33476 KB Output is correct
16 Correct 312 ms 33260 KB Output is correct
17 Correct 284 ms 34532 KB Output is correct
18 Correct 283 ms 33300 KB Output is correct
19 Correct 428 ms 35680 KB Output is correct
20 Correct 609 ms 36476 KB Output is correct
21 Correct 526 ms 36648 KB Output is correct
22 Partially correct 407 ms 37144 KB Output is partially correct
23 Correct 387 ms 36528 KB Output is correct
24 Partially correct 460 ms 37140 KB Output is partially correct
25 Partially correct 590 ms 37112 KB Output is partially correct
26 Partially correct 629 ms 37196 KB Output is partially correct
27 Partially correct 279 ms 27724 KB Output is partially correct
28 Partially correct 318 ms 27764 KB Output is partially correct
29 Correct 294 ms 27808 KB Output is correct
30 Correct 283 ms 27456 KB Output is correct
31 Correct 303 ms 27108 KB Output is correct
32 Correct 257 ms 27308 KB Output is correct
33 Correct 298 ms 27804 KB Output is correct
34 Partially correct 300 ms 28192 KB Output is partially correct
35 Partially correct 288 ms 27708 KB Output is partially correct
36 Partially correct 269 ms 28072 KB Output is partially correct
37 Partially correct 232 ms 28068 KB Output is partially correct
38 Correct 281 ms 28448 KB Output is correct
39 Correct 648 ms 36192 KB Output is correct
40 Correct 707 ms 36048 KB Output is correct
41 Partially correct 352 ms 36592 KB Output is partially correct
42 Partially correct 758 ms 36676 KB Output is partially correct