oj.uz

Submission #116988

# Submission time Handle Problem Language Result Execution time Memory
116988 2019-06-14T11:08:07 Z pzdba Highway Tolls (IOI18_highway) C++14
51 / 100
 358 ms 18220 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];
int k = 1;
void dfs(int u, int p, int j, int d, int t){
    par[u] = j;
    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);
        }
    }
    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;
        }
        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;
        }
        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:14: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:49: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 4636 KB Output is correct
2 Correct 5 ms 4636 KB Output is correct
3 Correct 5 ms 4552 KB Output is correct
4 Correct 6 ms 4556 KB Output is correct
5 Correct 6 ms 4472 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct
7 Correct 5 ms 4552 KB Output is correct
8 Correct 5 ms 4636 KB Output is correct
9 Correct 6 ms 4600 KB Output is correct
10 Correct 6 ms 4600 KB Output is correct
11 Correct 6 ms 4520 KB Output is correct
12 Correct 6 ms 4600 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4600 KB Output is correct
2 Correct 21 ms 5520 KB Output is correct
3 Correct 216 ms 13868 KB Output is correct
4 Correct 259 ms 13988 KB Output is correct
5 Correct 253 ms 13908 KB Output is correct
6 Correct 241 ms 13860 KB Output is correct
7 Correct 246 ms 13900 KB Output is correct
8 Correct 259 ms 13868 KB Output is correct
9 Correct 259 ms 13876 KB Output is correct
10 Correct 227 ms 13856 KB Output is correct
11 Correct 247 ms 13860 KB Output is correct
12 Correct 264 ms 14608 KB Output is correct
13 Correct 243 ms 14280 KB Output is correct
14 Correct 264 ms 14260 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6008 KB Output is correct
2 Correct 63 ms 7476 KB Output is correct
3 Correct 63 ms 8888 KB Output is correct
4 Correct 190 ms 16248 KB Output is correct
5 Correct 179 ms 16312 KB Output is correct
6 Correct 183 ms 17268 KB Output is correct
7 Correct 181 ms 18220 KB Output is correct
8 Correct 203 ms 16736 KB Output is correct
9 Correct 189 ms 16960 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 29 ms 5548 KB Output is correct
3 Correct 181 ms 11908 KB Output is correct
4 Correct 235 ms 13868 KB Output is correct
5 Correct 254 ms 13856 KB Output is correct
6 Correct 220 ms 13864 KB Output is correct
7 Correct 258 ms 13924 KB Output is correct
8 Correct 214 ms 13892 KB Output is correct
9 Correct 257 ms 13912 KB Output is correct
10 Correct 259 ms 13876 KB Output is correct
11 Correct 239 ms 13940 KB Output is correct
12 Correct 286 ms 14624 KB Output is correct
13 Correct 273 ms 14368 KB Output is correct
14 Correct 251 ms 14256 KB Output is correct
15 Correct 228 ms 13860 KB Output is correct
16 Correct 249 ms 13856 KB Output is correct
17 Correct 253 ms 14032 KB Output is correct
18 Correct 283 ms 14404 KB Output is correct
19 Correct 252 ms 13872 KB Output is correct
20 Correct 286 ms 14900 KB Output is correct
21 Correct 176 ms 14668 KB Output is correct
22 Correct 171 ms 14548 KB Output is correct
23 Correct 217 ms 14528 KB Output is correct
24 Correct 174 ms 14584 KB Output is correct
25 Correct 251 ms 17756 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5540 KB Output is correct
2 Correct 34 ms 5628 KB Output is correct
3 Correct 262 ms 14204 KB Output is correct
4 Correct 295 ms 14620 KB Output is correct
5 Correct 318 ms 15332 KB Output is correct
6 Correct 338 ms 15380 KB Output is correct
7 Correct 323 ms 15300 KB Output is correct
8 Correct 358 ms 15408 KB Output is correct
9 Incorrect 251 ms 11592 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 32 ms 5596 KB Output is correct
2 Correct 38 ms 5588 KB Output is correct
3 Correct 278 ms 14224 KB Output is correct
4 Correct 288 ms 14356 KB Output is correct
5 Correct 280 ms 14564 KB Output is correct
6 Correct 356 ms 15316 KB Output is correct
7 Correct 305 ms 14208 KB Output is correct
8 Correct 234 ms 14396 KB Output is correct
9 Incorrect 319 ms 14556 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -