oj.uz

Submission #114052

# Submission time Handle Problem Language Result Execution time Memory
114052 2019-05-29T17:46:35 Z thebes Highway Tolls (IOI18_highway) C++14
100 / 100
 868 ms 36848 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-1;
    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;
            }
        }
    }
    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:11: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:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m = lo+hi>>1;
                ~~^~~
highway.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
                   ~^~~~~~~~~~
highway.cpp:77:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:79: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 7392 KB Output is correct
2 Correct 9 ms 7392 KB Output is correct
3 Correct 8 ms 7392 KB Output is correct
4 Correct 9 ms 7288 KB Output is correct
5 Correct 8 ms 7384 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 8 ms 7468 KB Output is correct
8 Correct 8 ms 7388 KB Output is correct
9 Correct 9 ms 7288 KB Output is correct
10 Correct 8 ms 7392 KB Output is correct
11 Correct 9 ms 7392 KB Output is correct
12 Correct 8 ms 7476 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 42 ms 9840 KB Output is correct
3 Correct 509 ms 28404 KB Output is correct
4 Correct 531 ms 28344 KB Output is correct
5 Correct 577 ms 28732 KB Output is correct
6 Correct 443 ms 27524 KB Output is correct
7 Correct 447 ms 27428 KB Output is correct
8 Correct 576 ms 28776 KB Output is correct
9 Correct 440 ms 27400 KB Output is correct
10 Correct 534 ms 27800 KB Output is correct
11 Correct 410 ms 26588 KB Output is correct
12 Correct 546 ms 30824 KB Output is correct
13 Correct 575 ms 31348 KB Output is correct
14 Correct 609 ms 31524 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10636 KB Output is correct
2 Correct 63 ms 13616 KB Output is correct
3 Correct 67 ms 13296 KB Output is correct
4 Correct 281 ms 32220 KB Output is correct
5 Correct 291 ms 32244 KB Output is correct
6 Correct 259 ms 34740 KB Output is correct
7 Correct 209 ms 24128 KB Output is correct
8 Correct 262 ms 33396 KB Output is correct
9 Correct 237 ms 27144 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7544 KB Output is correct
2 Correct 51 ms 9520 KB Output is correct
3 Correct 413 ms 24272 KB Output is correct
4 Correct 491 ms 28232 KB Output is correct
5 Correct 365 ms 25812 KB Output is correct
6 Correct 361 ms 25704 KB Output is correct
7 Correct 482 ms 27360 KB Output is correct
8 Correct 349 ms 26052 KB Output is correct
9 Correct 574 ms 28592 KB Output is correct
10 Correct 523 ms 27676 KB Output is correct
11 Correct 556 ms 30932 KB Output is correct
12 Correct 541 ms 31152 KB Output is correct
13 Correct 506 ms 30164 KB Output is correct
14 Correct 413 ms 26944 KB Output is correct
15 Correct 388 ms 25920 KB Output is correct
16 Correct 337 ms 23996 KB Output is correct
17 Correct 539 ms 30744 KB Output is correct
18 Correct 567 ms 31680 KB Output is correct
19 Correct 326 ms 24384 KB Output is correct
20 Correct 364 ms 25680 KB Output is correct
21 Correct 441 ms 27544 KB Output is correct
22 Correct 364 ms 26324 KB Output is correct
23 Correct 513 ms 27972 KB Output is correct
24 Correct 500 ms 28568 KB Output is correct
25 Correct 579 ms 36208 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9936 KB Output is correct
2 Correct 51 ms 10120 KB Output is correct
3 Correct 609 ms 30352 KB Output is correct
4 Correct 668 ms 31276 KB Output is correct
5 Correct 868 ms 34684 KB Output is correct
6 Correct 819 ms 35140 KB Output is correct
7 Correct 835 ms 34812 KB Output is correct
8 Correct 789 ms 35124 KB Output is correct
9 Correct 520 ms 30016 KB Output is correct
10 Correct 659 ms 32164 KB Output is correct
11 Correct 651 ms 32328 KB Output is correct
12 Correct 848 ms 34064 KB Output is correct
13 Correct 812 ms 34572 KB Output is correct
14 Correct 817 ms 35148 KB Output is correct
15 Correct 814 ms 35520 KB Output is correct
16 Correct 663 ms 32576 KB Output is correct
17 Correct 460 ms 27816 KB Output is correct
18 Correct 361 ms 26600 KB Output is correct
19 Correct 487 ms 28796 KB Output is correct
20 Correct 426 ms 27448 KB Output is correct
21 Correct 840 ms 36184 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9876 KB Output is correct
2 Correct 50 ms 10164 KB Output is correct
3 Correct 627 ms 30168 KB Output is correct
4 Correct 664 ms 30724 KB Output is correct
5 Correct 690 ms 31564 KB Output is correct
6 Correct 800 ms 35496 KB Output is correct
7 Correct 640 ms 30556 KB Output is correct
8 Correct 646 ms 31268 KB Output is correct
9 Correct 677 ms 31456 KB Output is correct
10 Correct 762 ms 34908 KB Output is correct
11 Correct 805 ms 35048 KB Output is correct
12 Correct 760 ms 34988 KB Output is correct
13 Correct 542 ms 31124 KB Output is correct
14 Correct 555 ms 31108 KB Output is correct
15 Correct 658 ms 33276 KB Output is correct
16 Correct 637 ms 32220 KB Output is correct
17 Correct 655 ms 32380 KB Output is correct
18 Correct 652 ms 32164 KB Output is correct
19 Correct 765 ms 34016 KB Output is correct
20 Correct 780 ms 35012 KB Output is correct
21 Correct 796 ms 35128 KB Output is correct
22 Correct 794 ms 35008 KB Output is correct
23 Correct 820 ms 35180 KB Output is correct
24 Correct 783 ms 35184 KB Output is correct
25 Correct 779 ms 35288 KB Output is correct
26 Correct 854 ms 35528 KB Output is correct
27 Correct 442 ms 27604 KB Output is correct
28 Correct 490 ms 28524 KB Output is correct
29 Correct 510 ms 29412 KB Output is correct
30 Correct 549 ms 29144 KB Output is correct
31 Correct 479 ms 28660 KB Output is correct
32 Correct 459 ms 28588 KB Output is correct
33 Correct 487 ms 29348 KB Output is correct
34 Correct 426 ms 27880 KB Output is correct
35 Correct 466 ms 28052 KB Output is correct
36 Correct 507 ms 28652 KB Output is correct
37 Correct 480 ms 28496 KB Output is correct
38 Correct 562 ms 29452 KB Output is correct
39 Correct 794 ms 36604 KB Output is correct
40 Correct 818 ms 36848 KB Output is correct
41 Correct 790 ms 35956 KB Output is correct
42 Correct 767 ms 35468 KB Output is correct