oj.uz

Submission #114041

# Submission time Handle Problem Language Result Execution time Memory
114041 2019-05-29T17:32:41 Z thebes Highway Tolls (IOI18_highway) C++14
24 / 100
 929 ms 32956 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 = 1, 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;
            }
        }
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4576 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4472 KB Output is correct
4 Correct 6 ms 4600 KB Output is correct
5 Correct 6 ms 4472 KB Output is correct
6 Correct 6 ms 4572 KB Output is correct
7 Correct 6 ms 4568 KB Output is correct
8 Correct 6 ms 4568 KB Output is correct
9 Correct 6 ms 4520 KB Output is correct
10 Correct 6 ms 4472 KB Output is correct
11 Correct 6 ms 4472 KB Output is correct
12 Incorrect 6 ms 4472 KB Output is incorrect: {s, t} is wrong.

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4820 KB Output is correct
2 Correct 49 ms 6924 KB Output is correct
3 Correct 532 ms 25460 KB Output is correct
4 Correct 499 ms 25496 KB Output is correct
5 Correct 527 ms 25912 KB Output is correct
6 Correct 462 ms 24724 KB Output is correct
7 Correct 432 ms 24516 KB Output is correct
8 Correct 583 ms 26028 KB Output is correct
9 Correct 434 ms 24560 KB Output is correct
10 Correct 500 ms 24948 KB Output is correct
11 Correct 390 ms 23800 KB Output is correct
12 Correct 562 ms 28076 KB Output is correct
13 Correct 546 ms 28384 KB Output is correct
14 Incorrect 570 ms 28480 KB Output is incorrect: {s, t} is wrong.

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7816 KB Output is correct
2 Correct 60 ms 10840 KB Output is correct
3 Correct 97 ms 10524 KB Output is correct
4 Correct 263 ms 29376 KB Output is correct
5 Correct 253 ms 29420 KB Output is correct
6 Correct 260 ms 31996 KB Output is correct
7 Correct 192 ms 21228 KB Output is correct
8 Correct 247 ms 30620 KB Output is correct
9 Correct 264 ms 24384 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4744 KB Output is correct
2 Correct 35 ms 6868 KB Output is correct
3 Correct 393 ms 21564 KB Output is correct
4 Correct 512 ms 25408 KB Output is correct
5 Correct 352 ms 22976 KB Output is correct
6 Correct 354 ms 22900 KB Output is correct
7 Correct 437 ms 24544 KB Output is correct
8 Correct 369 ms 23244 KB Output is correct
9 Correct 547 ms 25588 KB Output is correct
10 Correct 482 ms 24812 KB Output is correct
11 Correct 534 ms 28104 KB Output is correct
12 Correct 540 ms 28340 KB Output is correct
13 Correct 530 ms 27224 KB Output is correct
14 Correct 410 ms 24068 KB Output is correct
15 Correct 359 ms 23072 KB Output is correct
16 Correct 339 ms 21156 KB Output is correct
17 Correct 515 ms 28056 KB Output is correct
18 Incorrect 545 ms 27820 KB Output is incorrect: {s, t} is wrong.
19 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7080 KB Output is correct
2 Correct 56 ms 7160 KB Output is correct
3 Correct 580 ms 27520 KB Output is correct
4 Correct 672 ms 28260 KB Output is correct
5 Correct 756 ms 31524 KB Output is correct
6 Correct 812 ms 32028 KB Output is correct
7 Correct 793 ms 31792 KB Output is correct
8 Correct 778 ms 31952 KB Output is correct
9 Correct 541 ms 27208 KB Output is correct
10 Correct 596 ms 29112 KB Output is correct
11 Correct 650 ms 29096 KB Output is correct
12 Correct 768 ms 31000 KB Output is correct
13 Correct 767 ms 31464 KB Output is correct
14 Correct 929 ms 31952 KB Output is correct
15 Correct 797 ms 32432 KB Output is correct
16 Correct 660 ms 29432 KB Output is correct
17 Correct 460 ms 25004 KB Output is correct
18 Correct 355 ms 23728 KB Output is correct
19 Correct 505 ms 25964 KB Output is correct
20 Correct 407 ms 24576 KB Output is correct
21 Correct 804 ms 32956 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7184 KB Output is correct
2 Correct 74 ms 7356 KB Output is correct
3 Correct 603 ms 27276 KB Output is correct
4 Correct 644 ms 27780 KB Output is correct
5 Correct 653 ms 28632 KB Output is correct
6 Correct 800 ms 32208 KB Output is correct
7 Correct 618 ms 27600 KB Output is correct
8 Correct 665 ms 28340 KB Output is correct
9 Correct 607 ms 28444 KB Output is correct
10 Correct 755 ms 31728 KB Output is correct
11 Correct 808 ms 31972 KB Output is correct
12 Correct 768 ms 31872 KB Output is correct
13 Correct 532 ms 28252 KB Output is correct
14 Incorrect 580 ms 28268 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -