oj.uz

Submission #113713

# Submission time Handle Problem Language Result Execution time Memory
113713 2019-05-28T02:07:52 Z zoooma13 Highway Tolls (IOI18_highway) C++14
69 / 100
 332 ms 15292 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

int n ,m;
vector <pair <int ,int>> adj[MAX_N];

vector <pair<int ,int>> nodes;
void bfs(int s ,int f){
    nodes.clear();

    queue <pair<int,int>> nxt;
    nxt.push({s ,f});

    while(!nxt.empty()){
        int u = nxt.front().first ,f = nxt.front().second; nxt.pop();
        nodes.push_back({u ,f});
        for(auto e : adj[u])
            nxt.push(e);
    }
}

vector <int> main_W;
int solve(int u ,int f ,long long dist){
    bfs(u ,f);
    int st = 0 ,en = nodes.size()-1 ,mid;
    while(st < en){
        mid = (st+en+1)>>1;
        vector <int> w = main_W;
        for(int i=mid; i<=en; i++)
            w[nodes[i].second] = 1;

        if(ask(w) != dist)
            st = mid;
        else
            en = mid-1;
    }
    return nodes[st].first;
}

vector <pair<int ,int>> t_adj[MAX_N];
void get_bfs_tree(int s){
    main_W.resize(m ,1);

    vector <bool> vis(n); vis[s] = 1;
    queue <int> nxt; nxt.push(s);
    while(!nxt.empty()){
        int u = nxt.front(); nxt.pop();
        for(auto e : adj[u])
            if(!vis[e.first]){
                vis[e.first] = 1;
                nxt.push(e.first);

                main_W[e.second] = 0;
                t_adj[u].push_back(e);
            }
    }
    for(int i=0; i<n; i++)
        swap(adj[i] ,t_adj[i]);
}

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

    vector <int> w(m ,0);
    long long dist = ask(w);
    int st = 0 ,en = m-1 ,mid;
    while(st < en){
        mid = (st+en)>>1;
        for(int i=st; i<=mid; i++)
            w[i] = 1;

        if(ask(w) != dist){
            en = mid;
            for(int i=st; i<=mid; i++)
                w[i] = 0;
        }
        else
            st = mid+1;
    }

    get_bfs_tree(U[en]);
    adj[U[en]].erase(find(adj[U[en]].begin() ,adj[U[en]].end() ,make_pair(V[en] ,en)));

    dist = ask(main_W);
    int s = solve(U[en] ,en ,dist);
    int t = solve(V[en] ,en ,dist);
    answer(s ,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4596 KB Output is correct
2 Correct 27 ms 5432 KB Output is correct
3 Correct 207 ms 12880 KB Output is correct
4 Correct 213 ms 13276 KB Output is correct
5 Correct 261 ms 13176 KB Output is correct
6 Correct 209 ms 12876 KB Output is correct
7 Correct 200 ms 13268 KB Output is correct
8 Correct 253 ms 13256 KB Output is correct
9 Correct 198 ms 12880 KB Output is correct
10 Correct 215 ms 13256 KB Output is correct
11 Correct 225 ms 13232 KB Output is correct
12 Correct 223 ms 13488 KB Output is correct
13 Correct 216 ms 13756 KB Output is correct
14 Correct 208 ms 13364 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5604 KB Output is correct
2 Correct 42 ms 6520 KB Output is correct
3 Correct 49 ms 7524 KB Output is correct
4 Correct 169 ms 13120 KB Output is correct
5 Correct 170 ms 13076 KB Output is correct
6 Correct 172 ms 13604 KB Output is correct
7 Correct 176 ms 13464 KB Output is correct
8 Correct 155 ms 13140 KB Output is correct
9 Correct 174 ms 13484 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4676 KB Output is correct
2 Correct 24 ms 5444 KB Output is correct
3 Correct 152 ms 11284 KB Output is correct
4 Correct 216 ms 13176 KB Output is correct
5 Correct 204 ms 12984 KB Output is correct
6 Correct 213 ms 12948 KB Output is correct
7 Correct 207 ms 12884 KB Output is correct
8 Correct 205 ms 12776 KB Output is correct
9 Correct 221 ms 12872 KB Output is correct
10 Correct 199 ms 12856 KB Output is correct
11 Correct 223 ms 13376 KB Output is correct
12 Correct 227 ms 13452 KB Output is correct
13 Correct 217 ms 13492 KB Output is correct
14 Correct 220 ms 13240 KB Output is correct
15 Correct 207 ms 13184 KB Output is correct
16 Correct 219 ms 12808 KB Output is correct
17 Correct 207 ms 13472 KB Output is correct
18 Correct 225 ms 13480 KB Output is correct
19 Correct 212 ms 12880 KB Output is correct
20 Correct 198 ms 13780 KB Output is correct
21 Correct 162 ms 13164 KB Output is correct
22 Correct 212 ms 13184 KB Output is correct
23 Correct 184 ms 11980 KB Output is correct
24 Correct 190 ms 12188 KB Output is correct
25 Correct 246 ms 13376 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5496 KB Output is correct
2 Correct 30 ms 5628 KB Output is correct
3 Correct 206 ms 13700 KB Output is correct
4 Correct 270 ms 13624 KB Output is correct
5 Correct 314 ms 14884 KB Output is correct
6 Correct 317 ms 14408 KB Output is correct
7 Correct 323 ms 14392 KB Output is correct
8 Correct 315 ms 14544 KB Output is correct
9 Correct 254 ms 11556 KB Output is correct
10 Correct 267 ms 12008 KB Output is correct
11 Correct 279 ms 12784 KB Output is correct
12 Correct 311 ms 13716 KB Output is correct
13 Correct 328 ms 13984 KB Output is correct
14 Correct 323 ms 14544 KB Output is correct
15 Correct 308 ms 14696 KB Output is correct
16 Correct 300 ms 12724 KB Output is correct
17 Correct 181 ms 12880 KB Output is correct
18 Correct 197 ms 13408 KB Output is correct
19 Correct 196 ms 12912 KB Output is correct
20 Correct 177 ms 13512 KB Output is correct
21 Correct 314 ms 15292 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5376 KB Output is correct
2 Correct 30 ms 5516 KB Output is correct
3 Correct 251 ms 13052 KB Output is correct
4 Correct 238 ms 13216 KB Output is correct
5 Correct 270 ms 13508 KB Output is correct
6 Correct 301 ms 14412 KB Output is correct
7 Correct 232 ms 13684 KB Output is correct
8 Correct 246 ms 13752 KB Output is correct
9 Correct 236 ms 13516 KB Output is correct
10 Partially correct 332 ms 14408 KB Output is partially correct
11 Correct 321 ms 14456 KB Output is correct
12 Correct 314 ms 14436 KB Output is correct
13 Correct 249 ms 12704 KB Output is correct
14 Incorrect 266 ms 12152 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -