oj.uz

Submission #118772

# Submission time Handle Problem Language Result Execution time Memory
118772 2019-06-19T17:31:32 Z someone_aa Highway Tolls (IOI18_highway) C++17
100 / 100
 421 ms 23264 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 150100;
int n, m;
vector<int>w;
vector<int>gs[maxn];
vector<pair<int,int> > g[maxn];

vector<int>gt[maxn];

int dist[maxn][2], parent[maxn][2];
int pind[maxn], x;
bool visited[maxn];

ll dista;
int type[maxn];
bool important[maxn];

vector<pair<int,int> > st[2];

void bfs(int u, int v) {
    visited[u] = visited[v] = true;
    queue<pair<int,int> > q;

    type[u] = 0;
    type[v] = 1;
    q.push(mp(u, 0));
    q.push(mp(v, 1));

    pind[u] = pind[v] = -1;

    st[0].pb(mp(u, x));
    st[1].pb(mp(v, x));

    while(!q.empty()) {
        int curr = q.front().first;
        int currtype = q.front().second;
        q.pop();

        for(auto i:g[curr]) {
            int ni = i.first, nind = i.second;
            if(visited[ni]) continue;

            visited[ni] = true;
            pind[ni] = nind;
            important[nind] = true;

            q.push(mp(ni, currtype));
            st[currtype].pb(mp(ni, nind));
        }
    }
}

int solve(int root, int d) {
    int li = 0;
    int ri = st[d].size() - 1;

    int answ = li;

    //cout<<d<<": \n";

    while(li <= ri) {
        int mid = (li + ri) / 2;

        vector<int>w(m, 0);
        for(int i=mid;i<st[d].size();i++) {
            w[st[d][i].second] = 1;
        }

        for(int i=0;i<m;i++) {
            if(!important[i]) w[i] = 1;
        }

        ll currdist = ask(w);
        //cout<<mid<<": "<<currdist<<"\n";
        if(currdist == dista) {
            ri = mid - 1;
        }
        else {
            li = mid + 1;
            answ = max(answ, mid);
        }

    }

    return st[d][answ].first;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N; m = U.size();
    int li=0, ri=m-1;

    for(int i=0;i<m;i++) {
        //ind[mp(U[i], V[i])] = ind[mp(V[i], U[i])] = i;
        gs[U[i]].pb(V[i]);
        gs[V[i]].pb(U[i]);

        g[U[i]].pb(mp(V[i], i));
        g[V[i]].pb(mp(U[i], i));

        w.pb(0);
    }

    dista = ask(w);
    while(li <= ri) {
        int mid = (li + ri) / 2;
        for(int i=0;i<=mid;i++) {
            w[i] = 1;
        }

        ll currdist = ask(w);

        for(int i=0;i<=mid;i++) {
            w[i] = 0;
        }

        if(currdist == dista) {
            li = mid + 1;
        }
        else {
            ri = mid - 1;
            x = mid;
        }
    }

    int u = U[x], v = V[x];
    important[x] = true;

    //cout<<u<<" "<<v<<"\n";

    bfs(u, v);
    //preprocess();

    //memset(visited,false,sizeof(visited));
    //cout<<"Ans: "<<xx<<" "<<yy<<"\n";
    answer(solve(u, 0), solve(v, 1));
}

Compilation message

highway.cpp: In function 'int solve(int, int)':
highway.cpp:70:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=mid;i<st[d].size();i++) {
                       ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10872 KB Output is correct
2 Correct 11 ms 10904 KB Output is correct
3 Correct 11 ms 11000 KB Output is correct
4 Correct 11 ms 10916 KB Output is correct
5 Correct 12 ms 10908 KB Output is correct
6 Correct 12 ms 10920 KB Output is correct
7 Correct 12 ms 10920 KB Output is correct
8 Correct 11 ms 10904 KB Output is correct
9 Correct 11 ms 10912 KB Output is correct
10 Correct 12 ms 10920 KB Output is correct
11 Correct 12 ms 10908 KB Output is correct
12 Correct 12 ms 10920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10952 KB Output is correct
2 Correct 34 ms 12072 KB Output is correct
3 Correct 279 ms 20752 KB Output is correct
4 Correct 260 ms 20740 KB Output is correct
5 Correct 242 ms 20736 KB Output is correct
6 Correct 235 ms 20712 KB Output is correct
7 Correct 251 ms 20728 KB Output is correct
8 Correct 217 ms 20720 KB Output is correct
9 Correct 238 ms 20760 KB Output is correct
10 Correct 249 ms 20756 KB Output is correct
11 Correct 266 ms 20152 KB Output is correct
12 Correct 236 ms 20264 KB Output is correct
13 Correct 237 ms 19996 KB Output is correct
14 Correct 248 ms 20376 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11896 KB Output is correct
2 Correct 52 ms 12988 KB Output is correct
3 Correct 73 ms 14028 KB Output is correct
4 Correct 183 ms 19956 KB Output is correct
5 Correct 200 ms 20076 KB Output is correct
6 Correct 209 ms 20376 KB Output is correct
7 Correct 209 ms 19960 KB Output is correct
8 Correct 204 ms 20040 KB Output is correct
9 Correct 190 ms 20152 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 36 ms 12016 KB Output is correct
3 Correct 184 ms 18800 KB Output is correct
4 Correct 242 ms 20700 KB Output is correct
5 Correct 238 ms 20684 KB Output is correct
6 Correct 243 ms 20736 KB Output is correct
7 Correct 259 ms 20624 KB Output is correct
8 Correct 242 ms 20660 KB Output is correct
9 Correct 236 ms 20788 KB Output is correct
10 Correct 258 ms 20776 KB Output is correct
11 Correct 261 ms 19996 KB Output is correct
12 Correct 269 ms 20384 KB Output is correct
13 Correct 215 ms 20624 KB Output is correct
14 Correct 274 ms 20028 KB Output is correct
15 Correct 221 ms 20736 KB Output is correct
16 Correct 252 ms 20720 KB Output is correct
17 Correct 209 ms 20380 KB Output is correct
18 Correct 267 ms 20024 KB Output is correct
19 Correct 231 ms 20732 KB Output is correct
20 Correct 257 ms 20140 KB Output is correct
21 Correct 214 ms 21692 KB Output is correct
22 Correct 224 ms 21708 KB Output is correct
23 Correct 216 ms 21176 KB Output is correct
24 Correct 221 ms 21076 KB Output is correct
25 Correct 271 ms 20640 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12096 KB Output is correct
2 Correct 40 ms 12132 KB Output is correct
3 Correct 280 ms 21352 KB Output is correct
4 Correct 319 ms 21916 KB Output is correct
5 Correct 371 ms 23104 KB Output is correct
6 Correct 357 ms 22864 KB Output is correct
7 Correct 374 ms 23252 KB Output is correct
8 Correct 360 ms 23264 KB Output is correct
9 Correct 278 ms 19276 KB Output is correct
10 Correct 243 ms 20040 KB Output is correct
11 Correct 283 ms 20580 KB Output is correct
12 Correct 363 ms 22140 KB Output is correct
13 Correct 353 ms 22884 KB Output is correct
14 Correct 389 ms 22916 KB Output is correct
15 Correct 376 ms 22996 KB Output is correct
16 Correct 302 ms 21192 KB Output is correct
17 Correct 223 ms 21708 KB Output is correct
18 Correct 236 ms 21816 KB Output is correct
19 Correct 216 ms 21656 KB Output is correct
20 Correct 240 ms 21796 KB Output is correct
21 Correct 359 ms 22712 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12088 KB Output is correct
2 Correct 33 ms 12136 KB Output is correct
3 Correct 288 ms 21296 KB Output is correct
4 Correct 305 ms 21592 KB Output is correct
5 Correct 311 ms 21920 KB Output is correct
6 Correct 351 ms 22828 KB Output is correct
7 Correct 296 ms 21156 KB Output is correct
8 Correct 284 ms 21572 KB Output is correct
9 Correct 344 ms 21812 KB Output is correct
10 Correct 360 ms 22960 KB Output is correct
11 Correct 357 ms 22972 KB Output is correct
12 Correct 377 ms 22876 KB Output is correct
13 Correct 305 ms 20172 KB Output is correct
14 Correct 258 ms 20032 KB Output is correct
15 Correct 289 ms 20236 KB Output is correct
16 Correct 274 ms 20020 KB Output is correct
17 Correct 299 ms 20156 KB Output is correct
18 Correct 253 ms 20012 KB Output is correct
19 Correct 358 ms 22128 KB Output is correct
20 Correct 401 ms 22708 KB Output is correct
21 Correct 389 ms 23236 KB Output is correct
22 Correct 376 ms 22924 KB Output is correct
23 Correct 421 ms 23248 KB Output is correct
24 Correct 378 ms 23232 KB Output is correct
25 Correct 374 ms 23016 KB Output is correct
26 Correct 372 ms 22980 KB Output is correct
27 Correct 214 ms 21840 KB Output is correct
28 Correct 215 ms 21616 KB Output is correct
29 Correct 235 ms 21916 KB Output is correct
30 Correct 212 ms 21728 KB Output is correct
31 Correct 241 ms 21704 KB Output is correct
32 Correct 207 ms 21548 KB Output is correct
33 Correct 211 ms 21912 KB Output is correct
34 Correct 234 ms 21760 KB Output is correct
35 Correct 230 ms 21696 KB Output is correct
36 Correct 210 ms 21524 KB Output is correct
37 Correct 236 ms 21836 KB Output is correct
38 Correct 232 ms 21732 KB Output is correct
39 Correct 358 ms 23192 KB Output is correct
40 Correct 363 ms 23012 KB Output is correct
41 Correct 344 ms 22728 KB Output is correct
42 Correct 378 ms 23148 KB Output is correct