oj.uz

Submission #292404

# Submission time Handle Problem Language Result Execution time Memory
292404 2020-09-06T22:23:31 Z zoooma13 Highway Tolls (IOI18_highway) C++14
90 / 100
 338 ms 19156 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

vector<vector <pair<int ,int>>> adj;

vector <pair<int ,int>> ver;
void dfs(int u ,int p=-1 ,int f=-1){
    for(auto&e : adj[u]) if(e.first != p)
        dfs(e.first ,u ,e.second);
    ver.push_back({u ,f});
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    adj.resize(N);
    for(int i=0; i<M; i++){
        adj[U[i]].push_back({V[i] ,i});
        adj[V[i]].push_back({U[i] ,i});
    }

    long long emp = ask(vector<int>(M ,0));

    int st = 0 ,en = M-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t(mid+1 ,1);
        t.resize(M);
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }

    int root = U[st];
    vector <int> intree(M ,1);

    queue <int> q{{root}};
    vector <bool> vis(N); vis[root] = 1;
    vector <vector<pair<int ,int>>> newadj(N);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto&e : adj[u]) if(!vis[e.first]){
            q.push(e.first);
            vis[e.first] = 1;
            intree[e.second] = 0;
            newadj[u].push_back({e.first ,e.second});
            newadj[e.first].push_back({u ,e.second});
        }
    }

    swap(adj ,newadj);

    int S ,T;
    ver.clear() ,dfs(root) ,ver.pop_back();
    st = 0 ,en = N-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t = intree;
        for(int i=st; i<=mid; i++)
            t[ ver[i].second ] = 1;
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }
    S = ver[st].first;
    ver.clear() ,dfs(S) ,ver.pop_back();
    st = 0 ,en = N-1 ,mid;
    while(st <= en){
        mid = (st+en)>>1;
        vector <int> t = intree;
        for(int i=st; i<=mid; i++)
            t[ ver[i].second ] = 1;
        if(ask(t) != emp)
            en = mid-1;
        else
            st = mid+1;
    }
    T = ver[st].first;
    answer(S ,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:56:26: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |     st = 0 ,en = N-1 ,mid;
      |                          ^
highway.cpp:69:26: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |     st = 0 ,en = N-1 ,mid;
      |                          ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 16 ms 1920 KB Output is correct
3 Correct 174 ms 14604 KB Output is correct
4 Correct 174 ms 14604 KB Output is correct
5 Correct 170 ms 14664 KB Output is correct
6 Correct 184 ms 14732 KB Output is correct
7 Correct 174 ms 14604 KB Output is correct
8 Correct 182 ms 14604 KB Output is correct
9 Correct 170 ms 14604 KB Output is correct
10 Correct 173 ms 14604 KB Output is correct
11 Correct 180 ms 14628 KB Output is correct
12 Correct 181 ms 15432 KB Output is correct
13 Correct 228 ms 14984 KB Output is correct
14 Correct 231 ms 14984 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2304 KB Output is correct
2 Correct 29 ms 4344 KB Output is correct
3 Correct 59 ms 6360 KB Output is correct
4 Correct 159 ms 17172 KB Output is correct
5 Correct 184 ms 17056 KB Output is correct
6 Correct 183 ms 18132 KB Output is correct
7 Correct 191 ms 19156 KB Output is correct
8 Correct 186 ms 17480 KB Output is correct
9 Correct 141 ms 17728 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 17 ms 1912 KB Output is correct
3 Correct 126 ms 11476 KB Output is correct
4 Correct 173 ms 14796 KB Output is correct
5 Correct 165 ms 14676 KB Output is correct
6 Correct 169 ms 14732 KB Output is correct
7 Correct 172 ms 14604 KB Output is correct
8 Correct 182 ms 14596 KB Output is correct
9 Correct 172 ms 14668 KB Output is correct
10 Correct 177 ms 14604 KB Output is correct
11 Correct 173 ms 14732 KB Output is correct
12 Correct 184 ms 15372 KB Output is correct
13 Correct 180 ms 15116 KB Output is correct
14 Correct 178 ms 15204 KB Output is correct
15 Correct 176 ms 14596 KB Output is correct
16 Correct 180 ms 14624 KB Output is correct
17 Correct 181 ms 14796 KB Output is correct
18 Correct 195 ms 15296 KB Output is correct
19 Correct 172 ms 14676 KB Output is correct
20 Correct 193 ms 15628 KB Output is correct
21 Correct 124 ms 15348 KB Output is correct
22 Correct 140 ms 15372 KB Output is correct
23 Correct 137 ms 15100 KB Output is correct
24 Correct 152 ms 15428 KB Output is correct
25 Correct 181 ms 18696 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2040 KB Output is correct
2 Correct 20 ms 1960 KB Output is correct
3 Correct 195 ms 14944 KB Output is correct
4 Correct 245 ms 15236 KB Output is correct
5 Correct 260 ms 16212 KB Output is correct
6 Correct 255 ms 16100 KB Output is correct
7 Correct 319 ms 16044 KB Output is correct
8 Correct 269 ms 16028 KB Output is correct
9 Correct 255 ms 9564 KB Output is correct
10 Correct 247 ms 9452 KB Output is correct
11 Correct 263 ms 11436 KB Output is correct
12 Correct 313 ms 14176 KB Output is correct
13 Correct 248 ms 15076 KB Output is correct
14 Correct 261 ms 15840 KB Output is correct
15 Correct 258 ms 15972 KB Output is correct
16 Correct 248 ms 10724 KB Output is correct
17 Correct 193 ms 15372 KB Output is correct
18 Correct 169 ms 15668 KB Output is correct
19 Correct 150 ms 15492 KB Output is correct
20 Correct 158 ms 15596 KB Output is correct
21 Correct 302 ms 16352 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2040 KB Output is correct
2 Correct 19 ms 2048 KB Output is correct
3 Correct 243 ms 14960 KB Output is correct
4 Partially correct 251 ms 15132 KB Output is partially correct
5 Partially correct 275 ms 15284 KB Output is partially correct
6 Partially correct 264 ms 16056 KB Output is partially correct
7 Correct 195 ms 15072 KB Output is correct
8 Correct 209 ms 15244 KB Output is correct
9 Partially correct 254 ms 15400 KB Output is partially correct
10 Partially correct 326 ms 16044 KB Output is partially correct
11 Partially correct 324 ms 16096 KB Output is partially correct
12 Partially correct 275 ms 16064 KB Output is partially correct
13 Correct 269 ms 11432 KB Output is correct
14 Correct 258 ms 9488 KB Output is correct
15 Correct 265 ms 10932 KB Output is correct
16 Correct 223 ms 9480 KB Output is correct
17 Correct 197 ms 11480 KB Output is correct
18 Correct 204 ms 9452 KB Output is correct
19 Partially correct 323 ms 14288 KB Output is partially correct
20 Partially correct 257 ms 15068 KB Output is partially correct
21 Partially correct 264 ms 15964 KB Output is partially correct
22 Correct 261 ms 15812 KB Output is correct
23 Partially correct 338 ms 15844 KB Output is partially correct
24 Partially correct 328 ms 15840 KB Output is partially correct
25 Partially correct 315 ms 15788 KB Output is partially correct
26 Correct 277 ms 15972 KB Output is correct
27 Correct 194 ms 15584 KB Output is correct
28 Correct 196 ms 15484 KB Output is correct
29 Partially correct 208 ms 15872 KB Output is partially correct
30 Partially correct 200 ms 15620 KB Output is partially correct
31 Correct 196 ms 15624 KB Output is correct
32 Correct 207 ms 15512 KB Output is correct
33 Partially correct 149 ms 15748 KB Output is partially correct
34 Partially correct 198 ms 15436 KB Output is partially correct
35 Partially correct 149 ms 15496 KB Output is partially correct
36 Partially correct 154 ms 15368 KB Output is partially correct
37 Partially correct 147 ms 15828 KB Output is partially correct
38 Correct 186 ms 15604 KB Output is correct
39 Partially correct 261 ms 16612 KB Output is partially correct
40 Partially correct 266 ms 16980 KB Output is partially correct
41 Partially correct 260 ms 16228 KB Output is partially correct
42 Partially correct 268 ms 16100 KB Output is partially correct