oj.uz

Submission #138174

# Submission time Handle Problem Language Result Execution time Memory
138174 2019-07-29T13:51:41 Z thebes Highway Tolls (IOI18_highway) C++14
100 / 100
 471 ms 38856 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;
            }
        }
    }
    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 of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     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]
   33 |         ll m = lo+hi>>1;
      |                ~~^~~
highway.cpp:58:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         ll mmm = lo+hi>>1;
      |                  ~~^~~
highway.cpp:60:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
      |                   ~^~~~~~~~~~
highway.cpp:78:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         ll mmm = lo+hi>>1;
      |                  ~~^~~
highway.cpp:80:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         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 3 ms 10832 KB Output is correct
2 Correct 4 ms 10832 KB Output is correct
3 Correct 3 ms 10832 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 2 ms 10832 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 3 ms 10832 KB Output is correct
8 Correct 3 ms 10832 KB Output is correct
9 Correct 3 ms 10832 KB Output is correct
10 Correct 2 ms 10832 KB Output is correct
11 Correct 2 ms 10832 KB Output is correct
12 Correct 2 ms 10832 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11088 KB Output is correct
2 Correct 27 ms 12952 KB Output is correct
3 Correct 299 ms 29704 KB Output is correct
4 Correct 302 ms 29576 KB Output is correct
5 Correct 366 ms 29928 KB Output is correct
6 Correct 265 ms 28760 KB Output is correct
7 Correct 302 ms 28536 KB Output is correct
8 Correct 335 ms 30024 KB Output is correct
9 Correct 269 ms 28808 KB Output is correct
10 Correct 279 ms 29200 KB Output is correct
11 Correct 196 ms 28032 KB Output is correct
12 Correct 322 ms 32508 KB Output is correct
13 Correct 286 ms 32820 KB Output is correct
14 Correct 298 ms 33152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13904 KB Output is correct
2 Correct 40 ms 16968 KB Output is correct
3 Correct 51 ms 16664 KB Output is correct
4 Correct 162 ms 35104 KB Output is correct
5 Correct 140 ms 35248 KB Output is correct
6 Correct 159 ms 37556 KB Output is correct
7 Correct 116 ms 27484 KB Output is correct
8 Correct 154 ms 36528 KB Output is correct
9 Correct 145 ms 30424 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10832 KB Output is correct
2 Correct 21 ms 12880 KB Output is correct
3 Correct 220 ms 26156 KB Output is correct
4 Correct 267 ms 29656 KB Output is correct
5 Correct 191 ms 27304 KB Output is correct
6 Correct 170 ms 27256 KB Output is correct
7 Correct 246 ms 28544 KB Output is correct
8 Correct 182 ms 27512 KB Output is correct
9 Correct 332 ms 29708 KB Output is correct
10 Correct 273 ms 28848 KB Output is correct
11 Correct 341 ms 32532 KB Output is correct
12 Correct 316 ms 32936 KB Output is correct
13 Correct 263 ms 31824 KB Output is correct
14 Correct 218 ms 28364 KB Output is correct
15 Correct 196 ms 27368 KB Output is correct
16 Correct 176 ms 27156 KB Output is correct
17 Correct 261 ms 32300 KB Output is correct
18 Correct 314 ms 33384 KB Output is correct
19 Correct 180 ms 27284 KB Output is correct
20 Correct 192 ms 27020 KB Output is correct
21 Correct 230 ms 29068 KB Output is correct
22 Correct 210 ms 28436 KB Output is correct
23 Correct 285 ms 29224 KB Output is correct
24 Correct 313 ms 29964 KB Output is correct
25 Correct 318 ms 38856 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13160 KB Output is correct
2 Correct 34 ms 13304 KB Output is correct
3 Correct 354 ms 31656 KB Output is correct
4 Correct 362 ms 33400 KB Output is correct
5 Correct 376 ms 35924 KB Output is correct
6 Correct 436 ms 36196 KB Output is correct
7 Correct 400 ms 36092 KB Output is correct
8 Correct 405 ms 36312 KB Output is correct
9 Correct 269 ms 32980 KB Output is correct
10 Correct 308 ms 34844 KB Output is correct
11 Correct 376 ms 34596 KB Output is correct
12 Correct 446 ms 35260 KB Output is correct
13 Correct 439 ms 35916 KB Output is correct
14 Correct 457 ms 36152 KB Output is correct
15 Correct 444 ms 36592 KB Output is correct
16 Correct 344 ms 34560 KB Output is correct
17 Correct 251 ms 29132 KB Output is correct
18 Correct 187 ms 28080 KB Output is correct
19 Correct 250 ms 30008 KB Output is correct
20 Correct 234 ms 29332 KB Output is correct
21 Correct 434 ms 37208 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13168 KB Output is correct
2 Correct 30 ms 13272 KB Output is correct
3 Correct 355 ms 31460 KB Output is correct
4 Correct 402 ms 32008 KB Output is correct
5 Correct 385 ms 32828 KB Output is correct
6 Correct 449 ms 36424 KB Output is correct
7 Correct 336 ms 31672 KB Output is correct
8 Correct 350 ms 32340 KB Output is correct
9 Correct 361 ms 32688 KB Output is correct
10 Correct 412 ms 36080 KB Output is correct
11 Correct 410 ms 36124 KB Output is correct
12 Correct 400 ms 36172 KB Output is correct
13 Correct 315 ms 33868 KB Output is correct
14 Correct 312 ms 34148 KB Output is correct
15 Correct 370 ms 35072 KB Output is correct
16 Correct 338 ms 34880 KB Output is correct
17 Correct 401 ms 34676 KB Output is correct
18 Correct 380 ms 35180 KB Output is correct
19 Correct 417 ms 35460 KB Output is correct
20 Correct 418 ms 36164 KB Output is correct
21 Correct 437 ms 36168 KB Output is correct
22 Correct 394 ms 36188 KB Output is correct
23 Correct 430 ms 36068 KB Output is correct
24 Correct 438 ms 36200 KB Output is correct
25 Correct 448 ms 36420 KB Output is correct
26 Correct 436 ms 36596 KB Output is correct
27 Correct 223 ms 28792 KB Output is correct
28 Correct 279 ms 30228 KB Output is correct
29 Correct 266 ms 30548 KB Output is correct
30 Correct 326 ms 30560 KB Output is correct
31 Correct 255 ms 30084 KB Output is correct
32 Correct 279 ms 29872 KB Output is correct
33 Correct 312 ms 30808 KB Output is correct
34 Correct 276 ms 29300 KB Output is correct
35 Correct 296 ms 29476 KB Output is correct
36 Correct 294 ms 30116 KB Output is correct
37 Correct 254 ms 29924 KB Output is correct
38 Correct 296 ms 30800 KB Output is correct
39 Correct 471 ms 38120 KB Output is correct
40 Correct 465 ms 37952 KB Output is correct
41 Correct 451 ms 37128 KB Output is correct
42 Correct 425 ms 36632 KB Output is correct