oj.uz

Submission #138822

# Submission time Handle Problem Language Result Execution time Memory
138822 2019-07-30T11:40:12 Z RockyB Highway Tolls (IOI18_highway) C++17
100 / 100
 890 ms 36892 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
 
typedef long long ll;
const int MN = 150005;
ll m, st, lo, hi, mm, i, x, y, vis[MN], s, t, d[MN], u[MN]; vector<int> q;
map<pair<ll,ll>,ll> id;
vector<ll> adj[MN], tr[MN], ls;
queue<ll> qq;
void sett(ll l){
    for(int i=0;i<q.size();i++)
        q[i]=(i<=l);
}
void dfs(ll n){
    for(auto v : tr[n]){
        ls.push_back(id[{v, n}]);
        d[v] = d[n]+1; dfs(v);
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    A = B = 0; m = U.size();
    for(i=0;i<m;i++) q.push_back(0);
    for(i=0;i<m;i++){
        x = U[i], y = V[i];
        id[{x,y}]=id[{y,x}]=i;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    st = ask(q);
    lo = 0, hi = m;
    while(lo<hi){
        ll m = lo+hi>>1;
        sett(m);
        bool heh = (ask(q)==st);
        if(heh) lo=m+1;
        else hi=m;
    }
    mm = lo-1; sett(mm);
    x = U[mm+1], y = V[mm+1];
    qq.push(x); qq.push(y); vis[x]=vis[y]=1;
    while(qq.size()){
        x = qq.front(); qq.pop();
        for(auto v : adj[x]){
            if(id[{x,v}]>mm&&!vis[v]){
                vis[v] = 1;
                qq.push(v);
                tr[x].push_back(v);
                u[id[{x,v}]]=1;
            }
        }
    }
  for (int i = 0; i <= N; i++) reverse(tr[i].begin(), tr[i].end());
    u[mm+1]=1;
    x = U[mm+1], y = V[mm+1];
    dfs(x);
    lo = 0; hi = ls.size();
    while(lo<hi){
        ll mmm = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==0){
        s = U[mm+1];
    }
    else{
        x = U[ls[lo-1]], y = V[ls[lo-1]];
        if(d[x]>d[y]) s = x;
        else s = y;
    }
    ls.clear();
    x = U[mm+1], y = V[mm+1];
    dfs(y);
    lo = 0; hi = ls.size();
    while(lo<hi){
        ll mmm = lo+hi>>1;
        for(i=0;i<m;i++) q[i]=!u[i];
        for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==0){
        t = V[mm+1];
    }
    else{
        x = U[ls[lo-1]], y = V[ls[lo-1]];
        if(d[x]>d[y]) t = x;
        else t = y;
    }
    answer(s, t);
}

Compilation message

highway.cpp: In function 'void sett(ll)':
highway.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++)
                 ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m = lo+hi>>1;
                ~~^~~
highway.cpp:59:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
                   ~^~~~~~~~~~
highway.cpp:79:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
                   ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7332 KB Output is correct
2 Correct 8 ms 7292 KB Output is correct
3 Correct 8 ms 7328 KB Output is correct
4 Correct 9 ms 7316 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 8 ms 7392 KB Output is correct
7 Correct 8 ms 7472 KB Output is correct
8 Correct 8 ms 7288 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7336 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 9 ms 7288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7556 KB Output is correct
2 Correct 50 ms 9848 KB Output is correct
3 Correct 549 ms 28468 KB Output is correct
4 Correct 640 ms 28244 KB Output is correct
5 Correct 512 ms 28776 KB Output is correct
6 Correct 463 ms 27608 KB Output is correct
7 Correct 443 ms 27344 KB Output is correct
8 Correct 532 ms 28780 KB Output is correct
9 Correct 453 ms 27368 KB Output is correct
10 Correct 530 ms 27792 KB Output is correct
11 Correct 385 ms 26584 KB Output is correct
12 Correct 586 ms 30844 KB Output is correct
13 Correct 563 ms 31296 KB Output is correct
14 Correct 570 ms 31352 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10536 KB Output is correct
2 Correct 65 ms 13564 KB Output is correct
3 Correct 79 ms 13284 KB Output is correct
4 Correct 276 ms 32128 KB Output is correct
5 Correct 260 ms 32244 KB Output is correct
6 Correct 291 ms 34652 KB Output is correct
7 Correct 245 ms 24064 KB Output is correct
8 Correct 259 ms 33452 KB Output is correct
9 Correct 250 ms 27172 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7640 KB Output is correct
2 Correct 52 ms 9712 KB Output is correct
3 Correct 432 ms 24236 KB Output is correct
4 Correct 574 ms 28220 KB Output is correct
5 Correct 340 ms 25796 KB Output is correct
6 Correct 354 ms 25720 KB Output is correct
7 Correct 443 ms 27268 KB Output is correct
8 Correct 405 ms 26192 KB Output is correct
9 Correct 568 ms 28488 KB Output is correct
10 Correct 497 ms 27676 KB Output is correct
11 Correct 559 ms 30888 KB Output is correct
12 Correct 566 ms 31184 KB Output is correct
13 Correct 524 ms 30052 KB Output is correct
14 Correct 409 ms 26908 KB Output is correct
15 Correct 356 ms 25916 KB Output is correct
16 Correct 349 ms 23996 KB Output is correct
17 Correct 554 ms 30844 KB Output is correct
18 Correct 594 ms 31788 KB Output is correct
19 Correct 327 ms 24436 KB Output is correct
20 Correct 375 ms 25688 KB Output is correct
21 Correct 548 ms 27564 KB Output is correct
22 Correct 482 ms 26404 KB Output is correct
23 Correct 519 ms 27856 KB Output is correct
24 Correct 510 ms 28528 KB Output is correct
25 Correct 640 ms 36108 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9920 KB Output is correct
2 Correct 57 ms 10068 KB Output is correct
3 Correct 640 ms 30408 KB Output is correct
4 Correct 647 ms 31384 KB Output is correct
5 Correct 770 ms 34576 KB Output is correct
6 Correct 817 ms 35108 KB Output is correct
7 Correct 804 ms 34924 KB Output is correct
8 Correct 765 ms 35204 KB Output is correct
9 Correct 515 ms 29988 KB Output is correct
10 Correct 615 ms 32152 KB Output is correct
11 Correct 671 ms 32272 KB Output is correct
12 Correct 764 ms 34132 KB Output is correct
13 Correct 793 ms 34488 KB Output is correct
14 Correct 829 ms 35156 KB Output is correct
15 Correct 823 ms 35508 KB Output is correct
16 Correct 696 ms 32616 KB Output is correct
17 Correct 494 ms 27844 KB Output is correct
18 Correct 344 ms 26556 KB Output is correct
19 Correct 511 ms 28776 KB Output is correct
20 Correct 424 ms 27416 KB Output is correct
21 Correct 802 ms 36088 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9876 KB Output is correct
2 Correct 70 ms 10148 KB Output is correct
3 Correct 626 ms 30160 KB Output is correct
4 Correct 595 ms 30724 KB Output is correct
5 Correct 655 ms 31600 KB Output is correct
6 Correct 782 ms 35296 KB Output is correct
7 Correct 585 ms 30548 KB Output is correct
8 Correct 653 ms 31280 KB Output is correct
9 Correct 640 ms 31576 KB Output is correct
10 Correct 831 ms 34928 KB Output is correct
11 Correct 814 ms 35044 KB Output is correct
12 Correct 831 ms 34904 KB Output is correct
13 Correct 538 ms 31032 KB Output is correct
14 Correct 535 ms 31104 KB Output is correct
15 Correct 634 ms 33172 KB Output is correct
16 Correct 607 ms 32192 KB Output is correct
17 Correct 664 ms 32348 KB Output is correct
18 Correct 610 ms 32024 KB Output is correct
19 Correct 734 ms 34000 KB Output is correct
20 Correct 797 ms 35028 KB Output is correct
21 Correct 814 ms 35076 KB Output is correct
22 Correct 817 ms 35108 KB Output is correct
23 Correct 793 ms 35168 KB Output is correct
24 Correct 850 ms 35264 KB Output is correct
25 Correct 890 ms 35384 KB Output is correct
26 Correct 825 ms 35468 KB Output is correct
27 Correct 512 ms 27488 KB Output is correct
28 Correct 552 ms 28636 KB Output is correct
29 Correct 531 ms 29424 KB Output is correct
30 Correct 547 ms 29140 KB Output is correct
31 Correct 504 ms 28580 KB Output is correct
32 Correct 488 ms 28580 KB Output is correct
33 Correct 577 ms 29392 KB Output is correct
34 Correct 481 ms 27836 KB Output is correct
35 Correct 475 ms 28052 KB Output is correct
36 Correct 497 ms 28712 KB Output is correct
37 Correct 451 ms 28532 KB Output is correct
38 Correct 529 ms 29384 KB Output is correct
39 Correct 810 ms 36564 KB Output is correct
40 Correct 837 ms 36892 KB Output is correct
41 Correct 837 ms 35968 KB Output is correct
42 Correct 831 ms 35476 KB Output is correct