oj.uz

Submission #114038

# Submission time Handle Problem Language Result Execution time Memory
114038 2019-05-29T17:14:23 Z thebes Highway Tolls (IOI18_highway) C++14
6 / 100
 801 ms 32364 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+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==ls.size()){
        s = U[mm+1];
    }
    else{
        x = U[ls[lo]], y = V[ls[lo]];
        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+1;i<ls.size();i++) q[ls[i]]=1;
        bool heh = (ask(q)==st);
        if(heh) hi=mmm;
        else lo=mmm+1;
    }
    if(lo==ls.size()){
        t = V[mm+1];
    }
    else{
        x = U[ls[lo]], y = V[ls[lo]];
        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:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
                     ~^~~~~~~~~~
highway.cpp:64:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(lo==ls.size()){
        ~~^~~~~~~~~~~
highway.cpp:77:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mmm = lo+hi>>1;
                  ~~^~~
highway.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
                     ~^~~~~~~~~~
highway.cpp:84:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(lo==ls.size()){
        ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4568 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4728 KB Output is correct
2 Correct 45 ms 6952 KB Output is correct
3 Correct 493 ms 25464 KB Output is correct
4 Correct 518 ms 25464 KB Output is correct
5 Correct 573 ms 25908 KB Output is correct
6 Correct 470 ms 24680 KB Output is correct
7 Correct 445 ms 24460 KB Output is correct
8 Correct 557 ms 25924 KB Output is correct
9 Correct 492 ms 24564 KB Output is correct
10 Correct 470 ms 24928 KB Output is correct
11 Correct 371 ms 23744 KB Output is correct
12 Correct 582 ms 27980 KB Output is correct
13 Correct 538 ms 28500 KB Output is correct
14 Incorrect 534 ms 28360 KB Output is incorrect: {s, t} is wrong.

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7800 KB Output is correct
2 Correct 54 ms 10800 KB Output is correct
3 Correct 75 ms 10484 KB Output is correct
4 Correct 265 ms 29288 KB Output is correct
5 Correct 268 ms 29416 KB Output is correct
6 Correct 290 ms 31844 KB Output is correct
7 Correct 226 ms 21372 KB Output is correct
8 Correct 269 ms 30620 KB Output is correct
9 Correct 256 ms 24320 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4816 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7100 KB Output is correct
2 Correct 49 ms 7320 KB Output is correct
3 Correct 609 ms 27452 KB Output is correct
4 Correct 618 ms 28328 KB Output is correct
5 Correct 757 ms 31468 KB Output is correct
6 Correct 782 ms 31932 KB Output is correct
7 Correct 785 ms 31708 KB Output is correct
8 Correct 788 ms 31976 KB Output is correct
9 Incorrect 482 ms 27132 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7104 KB Output is correct
2 Correct 58 ms 7348 KB Output is correct
3 Correct 609 ms 27228 KB Output is correct
4 Correct 664 ms 27724 KB Output is correct
5 Correct 669 ms 28600 KB Output is correct
6 Incorrect 801 ms 32364 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -