oj.uz

Submission #118792

# Submission time Handle Problem Language Result Execution time Memory
118792 2019-06-19T18:14:33 Z someone_aa Highway Tolls (IOI18_highway) C++17
100 / 100
 417 ms 23356 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);

        //cout<<li<<", "<<ri<<" mid: "<<mid<<" --> "<<currdist<<"\n";

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

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

    }

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

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

    //memset(visited,false,sizeof(visited));
    int xx = solve(u, 0);
    int yy = solve(v, 1);
    answer(xx, yy);
}

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 12 ms 10984 KB Output is correct
2 Correct 12 ms 10872 KB Output is correct
3 Correct 11 ms 10872 KB Output is correct
4 Correct 14 ms 10900 KB Output is correct
5 Correct 11 ms 10908 KB Output is correct
6 Correct 12 ms 10860 KB Output is correct
7 Correct 11 ms 10904 KB Output is correct
8 Correct 12 ms 10872 KB Output is correct
9 Correct 23 ms 10872 KB Output is correct
10 Correct 11 ms 10872 KB Output is correct
11 Correct 12 ms 10920 KB Output is correct
12 Correct 12 ms 11000 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11000 KB Output is correct
2 Correct 34 ms 11992 KB Output is correct
3 Correct 274 ms 20648 KB Output is correct
4 Correct 250 ms 20748 KB Output is correct
5 Correct 248 ms 20720 KB Output is correct
6 Correct 237 ms 20704 KB Output is correct
7 Correct 245 ms 20728 KB Output is correct
8 Correct 251 ms 20720 KB Output is correct
9 Correct 237 ms 20716 KB Output is correct
10 Correct 232 ms 20720 KB Output is correct
11 Correct 275 ms 20160 KB Output is correct
12 Correct 243 ms 20296 KB Output is correct
13 Correct 266 ms 20036 KB Output is correct
14 Correct 279 ms 20504 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12072 KB Output is correct
2 Correct 46 ms 12960 KB Output is correct
3 Correct 74 ms 14020 KB Output is correct
4 Correct 175 ms 19976 KB Output is correct
5 Correct 183 ms 19964 KB Output is correct
6 Correct 184 ms 20368 KB Output is correct
7 Correct 182 ms 20004 KB Output is correct
8 Correct 189 ms 20108 KB Output is correct
9 Correct 190 ms 20196 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11048 KB Output is correct
2 Correct 36 ms 12036 KB Output is correct
3 Correct 186 ms 18820 KB Output is correct
4 Correct 248 ms 20700 KB Output is correct
5 Correct 235 ms 20696 KB Output is correct
6 Correct 257 ms 20732 KB Output is correct
7 Correct 246 ms 20728 KB Output is correct
8 Correct 244 ms 20676 KB Output is correct
9 Correct 268 ms 20736 KB Output is correct
10 Correct 256 ms 20764 KB Output is correct
11 Correct 249 ms 20028 KB Output is correct
12 Correct 282 ms 20392 KB Output is correct
13 Correct 260 ms 20624 KB Output is correct
14 Correct 264 ms 20032 KB Output is correct
15 Correct 237 ms 20744 KB Output is correct
16 Correct 249 ms 20640 KB Output is correct
17 Correct 264 ms 20372 KB Output is correct
18 Correct 266 ms 20028 KB Output is correct
19 Correct 248 ms 20748 KB Output is correct
20 Correct 261 ms 20116 KB Output is correct
21 Correct 190 ms 21700 KB Output is correct
22 Correct 217 ms 21704 KB Output is correct
23 Correct 227 ms 21176 KB Output is correct
24 Correct 236 ms 21084 KB Output is correct
25 Correct 237 ms 20636 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11996 KB Output is correct
2 Correct 41 ms 12076 KB Output is correct
3 Correct 306 ms 21384 KB Output is correct
4 Correct 325 ms 21924 KB Output is correct
5 Correct 410 ms 23172 KB Output is correct
6 Correct 379 ms 22944 KB Output is correct
7 Correct 379 ms 23356 KB Output is correct
8 Correct 407 ms 23308 KB Output is correct
9 Correct 303 ms 19328 KB Output is correct
10 Correct 293 ms 20036 KB Output is correct
11 Correct 238 ms 20636 KB Output is correct
12 Correct 361 ms 22136 KB Output is correct
13 Correct 405 ms 22904 KB Output is correct
14 Correct 417 ms 22920 KB Output is correct
15 Correct 378 ms 22996 KB Output is correct
16 Correct 333 ms 20948 KB Output is correct
17 Correct 197 ms 21568 KB Output is correct
18 Correct 213 ms 21812 KB Output is correct
19 Correct 237 ms 21672 KB Output is correct
20 Correct 208 ms 21840 KB Output is correct
21 Correct 361 ms 22832 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12024 KB Output is correct
2 Correct 42 ms 12072 KB Output is correct
3 Correct 312 ms 21292 KB Output is correct
4 Correct 326 ms 21588 KB Output is correct
5 Correct 335 ms 21924 KB Output is correct
6 Correct 407 ms 22824 KB Output is correct
7 Correct 298 ms 21168 KB Output is correct
8 Correct 330 ms 21572 KB Output is correct
9 Correct 348 ms 21796 KB Output is correct
10 Correct 384 ms 22968 KB Output is correct
11 Correct 400 ms 22972 KB Output is correct
12 Correct 352 ms 22880 KB Output is correct
13 Correct 313 ms 20196 KB Output is correct
14 Correct 296 ms 20056 KB Output is correct
15 Correct 281 ms 20236 KB Output is correct
16 Correct 283 ms 20052 KB Output is correct
17 Correct 295 ms 20128 KB Output is correct
18 Correct 294 ms 19996 KB Output is correct
19 Correct 381 ms 22136 KB Output is correct
20 Correct 377 ms 22684 KB Output is correct
21 Correct 399 ms 23236 KB Output is correct
22 Correct 387 ms 22924 KB Output is correct
23 Correct 384 ms 23324 KB Output is correct
24 Correct 372 ms 23244 KB Output is correct
25 Correct 357 ms 22992 KB Output is correct
26 Correct 372 ms 22992 KB Output is correct
27 Correct 236 ms 21824 KB Output is correct
28 Correct 235 ms 21576 KB Output is correct
29 Correct 230 ms 21924 KB Output is correct
30 Correct 229 ms 21712 KB Output is correct
31 Correct 240 ms 21664 KB Output is correct
32 Correct 247 ms 21580 KB Output is correct
33 Correct 222 ms 21924 KB Output is correct
34 Correct 248 ms 21784 KB Output is correct
35 Correct 227 ms 21688 KB Output is correct
36 Correct 217 ms 21492 KB Output is correct
37 Correct 217 ms 21856 KB Output is correct
38 Correct 231 ms 21736 KB Output is correct
39 Correct 369 ms 23184 KB Output is correct
40 Correct 367 ms 23052 KB Output is correct
41 Correct 366 ms 22720 KB Output is correct
42 Correct 380 ms 23160 KB Output is correct