oj.uz

Submission #114045

# Submission time Handle Problem Language Result Execution time Memory
114045 2019-05-29T17:38:41 Z thebes Highway Tolls (IOI18_highway) C++14
69 / 100
 817 ms 33316 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int MN = 9e4+4, MM = 1.3e5+5;
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 6 ms 4472 KB Output is correct
2 Correct 5 ms 4572 KB Output is correct
3 Correct 6 ms 4576 KB Output is correct
4 Correct 6 ms 4472 KB Output is correct
5 Correct 6 ms 4568 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct
7 Correct 6 ms 4568 KB Output is correct
8 Correct 6 ms 4540 KB Output is correct
9 Correct 6 ms 4472 KB Output is correct
10 Correct 6 ms 4560 KB Output is correct
11 Correct 4 ms 4568 KB Output is correct
12 Correct 6 ms 4660 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4824 KB Output is correct
2 Correct 44 ms 7020 KB Output is correct
3 Correct 491 ms 25432 KB Output is correct
4 Correct 512 ms 25496 KB Output is correct
5 Correct 576 ms 25904 KB Output is correct
6 Correct 450 ms 24684 KB Output is correct
7 Correct 457 ms 24408 KB Output is correct
8 Correct 564 ms 25932 KB Output is correct
9 Correct 465 ms 24560 KB Output is correct
10 Correct 552 ms 25060 KB Output is correct
11 Correct 371 ms 23808 KB Output is correct
12 Correct 576 ms 28048 KB Output is correct
13 Correct 574 ms 28376 KB Output is correct
14 Correct 637 ms 28724 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7736 KB Output is correct
2 Correct 61 ms 10812 KB Output is correct
3 Correct 92 ms 10472 KB Output is correct
4 Correct 277 ms 29272 KB Output is correct
5 Correct 281 ms 29496 KB Output is correct
6 Correct 287 ms 31916 KB Output is correct
7 Correct 218 ms 21216 KB Output is correct
8 Correct 258 ms 30608 KB Output is correct
9 Correct 216 ms 24416 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4776 KB Output is correct
2 Correct 41 ms 6760 KB Output is correct
3 Correct 373 ms 21432 KB Output is correct
4 Correct 484 ms 25416 KB Output is correct
5 Correct 353 ms 22952 KB Output is correct
6 Correct 380 ms 22892 KB Output is correct
7 Correct 443 ms 24428 KB Output is correct
8 Correct 371 ms 23244 KB Output is correct
9 Correct 532 ms 25620 KB Output is correct
10 Correct 489 ms 24956 KB Output is correct
11 Correct 565 ms 27976 KB Output is correct
12 Correct 547 ms 28332 KB Output is correct
13 Correct 512 ms 27220 KB Output is correct
14 Correct 382 ms 24144 KB Output is correct
15 Correct 348 ms 23064 KB Output is correct
16 Correct 321 ms 21236 KB Output is correct
17 Correct 541 ms 27848 KB Output is correct
18 Correct 549 ms 28908 KB Output is correct
19 Correct 344 ms 21596 KB Output is correct
20 Correct 367 ms 22848 KB Output is correct
21 Correct 544 ms 24608 KB Output is correct
22 Correct 409 ms 23492 KB Output is correct
23 Correct 498 ms 25120 KB Output is correct
24 Correct 515 ms 25684 KB Output is correct
25 Correct 552 ms 33316 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7104 KB Output is correct
2 Correct 68 ms 7240 KB Output is correct
3 Correct 615 ms 27448 KB Output is correct
4 Correct 639 ms 28372 KB Output is correct
5 Correct 751 ms 31592 KB Output is correct
6 Correct 783 ms 31984 KB Output is correct
7 Correct 763 ms 31712 KB Output is correct
8 Correct 715 ms 31956 KB Output is correct
9 Correct 495 ms 27276 KB Output is correct
10 Correct 600 ms 29088 KB Output is correct
11 Correct 672 ms 29132 KB Output is correct
12 Correct 747 ms 31020 KB Output is correct
13 Correct 807 ms 31412 KB Output is correct
14 Correct 817 ms 31956 KB Output is correct
15 Correct 758 ms 32312 KB Output is correct
16 Correct 616 ms 29584 KB Output is correct
17 Correct 474 ms 24988 KB Output is correct
18 Correct 458 ms 23728 KB Output is correct
19 Correct 479 ms 25968 KB Output is correct
20 Correct 402 ms 24568 KB Output is correct
21 Correct 804 ms 32936 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7108 KB Output is correct
2 Correct 72 ms 7348 KB Output is correct
3 Correct 636 ms 27220 KB Output is correct
4 Correct 653 ms 27796 KB Output is correct
5 Correct 635 ms 28512 KB Output is correct
6 Correct 815 ms 32172 KB Output is correct
7 Correct 604 ms 27672 KB Output is correct
8 Correct 744 ms 28316 KB Output is correct
9 Correct 659 ms 28468 KB Output is correct
10 Correct 749 ms 31768 KB Output is correct
11 Correct 778 ms 31956 KB Output is correct
12 Correct 791 ms 31836 KB Output is correct
13 Correct 574 ms 28168 KB Output is correct
14 Incorrect 566 ms 28296 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -