oj.uz

Submission #116990

# Submission time Handle Problem Language Result Execution time Memory
116990 2019-06-14T11:18:46 Z pzdba Highway Tolls (IOI18_highway) C++14
100 / 100
 403 ms 18224 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
vector<pii> g[90005], g2[90005];
bool vis[90005];
int arr[2][90005];
int par[90005];
bool mark[130005];
int k = 1;
void dfs(int u, int p, int j, int d, int t){
    par[u] = j;
    if(p != -1) mark[j] = 1;
    arr[t][k++] = u;
    for(int i=0;i<g2[u].size();i++){
        int v = g2[u][i].first, j = g2[u][i].second;
        if(v == p) continue;
        dfs(v, u, j, d+1, t);
    }
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
    int s, t;
    int m = U.size();
    for(int i=0;i<m;i++){
        int a = U[i], b = V[i];
        g[a].push_back(pii(b, i));
        g[b].push_back(pii(a, i));
    }
    vector<int> w;
    w.resize(m);
    LL base = ask(w);
    int lo = 0, hi = m-1, j = 0;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int i=0;i<=mid;i++) w[i] = 1;
        LL tmp = ask(w);
        if(tmp > base) j = mid, hi = mid-1;
        else lo = mid+1;
    }
    int u = U[j], v = V[j];
    vis[u] = 1;
    vis[v] = 1;
    queue<int> q;
    q.push(u);
    q.push(v);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i].first, j = g[u][i].second;
            if(vis[v]) continue;
            vis[v] = 1;
            g2[u].push_back(pii(v, j));
            g2[v].push_back(pii(u, j));
            q.push(v);
        }
    }
    mark[j] = 1;

    k = 1;
    dfs(u, -1, 0, 0, 0);
    int sz1 = k-1;

    k = 1;
    dfs(v, -1, 0, 0, 1);
    int sz2 = k-1;

    s = u, t = v;
    lo = 2, hi = sz1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int i=mid;i<=sz1;i++){
            int u = arr[0][i];
            w[par[u]] = 1;
        }
        for(int j=0;j<m;j++){
            if(mark[j]) continue;
            w[j] = 1;
        }
        LL tmp = ask(w);
        if(tmp > base) s = arr[0][mid], lo = mid+1;
        else hi = mid-1;
    }
    lo = 2, hi = sz2;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        for(int i=0;i<m;i++) w[i] = 0;
        for(int i=mid;i<=sz2;i++){
            int u = arr[1][i];
            w[par[u]] = 1;
        }
        for(int j=0;j<m;j++){
            if(mark[j]) continue;
            w[j] = 1;
        }
        LL tmp = ask(w);
        if(tmp > base) t = arr[1][mid], lo = mid+1;
        else hi = mid-1;
    }
    answer(s, t);
}

Compilation message

highway.cpp: In function 'void dfs(int, int, int, int, int)':
highway.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g2[u].size();i++){
                 ~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[u].size();i++){
                     ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4560 KB Output is correct
2 Correct 6 ms 4652 KB Output is correct
3 Correct 5 ms 4472 KB Output is correct
4 Correct 5 ms 4552 KB Output is correct
5 Correct 6 ms 4552 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct
7 Correct 6 ms 4552 KB Output is correct
8 Correct 6 ms 4472 KB Output is correct
9 Correct 6 ms 4556 KB Output is correct
10 Correct 6 ms 4552 KB Output is correct
11 Correct 6 ms 4560 KB Output is correct
12 Correct 5 ms 4552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4684 KB Output is correct
2 Correct 24 ms 5508 KB Output is correct
3 Correct 233 ms 13964 KB Output is correct
4 Correct 263 ms 14060 KB Output is correct
5 Correct 273 ms 13964 KB Output is correct
6 Correct 235 ms 13944 KB Output is correct
7 Correct 258 ms 14000 KB Output is correct
8 Correct 270 ms 13968 KB Output is correct
9 Correct 231 ms 14056 KB Output is correct
10 Correct 247 ms 13952 KB Output is correct
11 Correct 300 ms 14068 KB Output is correct
12 Correct 271 ms 14772 KB Output is correct
13 Correct 261 ms 14256 KB Output is correct
14 Correct 265 ms 14368 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6032 KB Output is correct
2 Correct 54 ms 7452 KB Output is correct
3 Correct 67 ms 8972 KB Output is correct
4 Correct 191 ms 16336 KB Output is correct
5 Correct 226 ms 16500 KB Output is correct
6 Correct 187 ms 17380 KB Output is correct
7 Correct 181 ms 18224 KB Output is correct
8 Correct 182 ms 16920 KB Output is correct
9 Correct 192 ms 17044 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4632 KB Output is correct
2 Correct 29 ms 5516 KB Output is correct
3 Correct 169 ms 11932 KB Output is correct
4 Correct 220 ms 13948 KB Output is correct
5 Correct 256 ms 14052 KB Output is correct
6 Correct 205 ms 13996 KB Output is correct
7 Correct 256 ms 13960 KB Output is correct
8 Correct 267 ms 13948 KB Output is correct
9 Correct 241 ms 13948 KB Output is correct
10 Correct 259 ms 13968 KB Output is correct
11 Correct 242 ms 14020 KB Output is correct
12 Correct 273 ms 14700 KB Output is correct
13 Correct 277 ms 14464 KB Output is correct
14 Correct 269 ms 14360 KB Output is correct
15 Correct 246 ms 14076 KB Output is correct
16 Correct 267 ms 14068 KB Output is correct
17 Correct 267 ms 14236 KB Output is correct
18 Correct 282 ms 14612 KB Output is correct
19 Correct 254 ms 13948 KB Output is correct
20 Correct 308 ms 15152 KB Output is correct
21 Correct 142 ms 14752 KB Output is correct
22 Correct 184 ms 14760 KB Output is correct
23 Correct 184 ms 14484 KB Output is correct
24 Correct 172 ms 14668 KB Output is correct
25 Correct 324 ms 17836 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5540 KB Output is correct
2 Correct 33 ms 5672 KB Output is correct
3 Correct 291 ms 14284 KB Output is correct
4 Correct 304 ms 14668 KB Output is correct
5 Correct 347 ms 15432 KB Output is correct
6 Correct 374 ms 15528 KB Output is correct
7 Correct 303 ms 15440 KB Output is correct
8 Correct 375 ms 15520 KB Output is correct
9 Correct 249 ms 11620 KB Output is correct
10 Correct 273 ms 11816 KB Output is correct
11 Correct 236 ms 12792 KB Output is correct
12 Correct 358 ms 14308 KB Output is correct
13 Correct 369 ms 14912 KB Output is correct
14 Correct 378 ms 15212 KB Output is correct
15 Correct 369 ms 15224 KB Output is correct
16 Correct 280 ms 12660 KB Output is correct
17 Correct 223 ms 14868 KB Output is correct
18 Correct 258 ms 14964 KB Output is correct
19 Correct 198 ms 14860 KB Output is correct
20 Correct 251 ms 14912 KB Output is correct
21 Correct 385 ms 15724 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5608 KB Output is correct
2 Correct 33 ms 5580 KB Output is correct
3 Correct 282 ms 14308 KB Output is correct
4 Correct 336 ms 14452 KB Output is correct
5 Correct 271 ms 14648 KB Output is correct
6 Correct 403 ms 15444 KB Output is correct
7 Correct 272 ms 14408 KB Output is correct
8 Correct 305 ms 14504 KB Output is correct
9 Correct 325 ms 14660 KB Output is correct
10 Correct 372 ms 15456 KB Output is correct
11 Correct 382 ms 15452 KB Output is correct
12 Correct 361 ms 15528 KB Output is correct
13 Correct 269 ms 12748 KB Output is correct
14 Correct 275 ms 11820 KB Output is correct
15 Correct 255 ms 12720 KB Output is correct
16 Correct 211 ms 11872 KB Output is correct
17 Correct 278 ms 12744 KB Output is correct
18 Correct 240 ms 11800 KB Output is correct
19 Correct 364 ms 14384 KB Output is correct
20 Correct 354 ms 14836 KB Output is correct
21 Correct 364 ms 15224 KB Output is correct
22 Correct 365 ms 15204 KB Output is correct
23 Correct 378 ms 15220 KB Output is correct
24 Correct 360 ms 15228 KB Output is correct
25 Correct 348 ms 15300 KB Output is correct
26 Correct 378 ms 15224 KB Output is correct
27 Correct 231 ms 14888 KB Output is correct
28 Correct 251 ms 14840 KB Output is correct
29 Correct 234 ms 15228 KB Output is correct
30 Correct 210 ms 14916 KB Output is correct
31 Correct 224 ms 14936 KB Output is correct
32 Correct 232 ms 14748 KB Output is correct
33 Correct 226 ms 15216 KB Output is correct
34 Correct 246 ms 14876 KB Output is correct
35 Correct 224 ms 14852 KB Output is correct
36 Correct 260 ms 14872 KB Output is correct
37 Correct 253 ms 15136 KB Output is correct
38 Correct 225 ms 14876 KB Output is correct
39 Correct 362 ms 15964 KB Output is correct
40 Correct 370 ms 16224 KB Output is correct
41 Correct 377 ms 15592 KB Output is correct
42 Correct 318 ms 15552 KB Output is correct