oj.uz

Submission #118782

# Submission time Handle Problem Language Result Execution time Memory
118782 2019-06-19T17:46:41 Z someone_aa Highway Tolls (IOI18_highway) C++17
100 / 100
 421 ms 23344 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<<": "<<currdist<<"\n";

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11064 KB Output is correct
2 Correct 34 ms 12024 KB Output is correct
3 Correct 252 ms 20740 KB Output is correct
4 Correct 228 ms 20732 KB Output is correct
5 Correct 259 ms 20748 KB Output is correct
6 Correct 246 ms 20712 KB Output is correct
7 Correct 214 ms 20736 KB Output is correct
8 Correct 244 ms 20728 KB Output is correct
9 Correct 254 ms 20716 KB Output is correct
10 Correct 239 ms 20712 KB Output is correct
11 Correct 262 ms 20152 KB Output is correct
12 Correct 236 ms 20188 KB Output is correct
13 Correct 255 ms 20004 KB Output is correct
14 Correct 248 ms 20380 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11944 KB Output is correct
2 Correct 53 ms 12960 KB Output is correct
3 Correct 70 ms 14032 KB Output is correct
4 Correct 187 ms 19968 KB Output is correct
5 Correct 201 ms 19960 KB Output is correct
6 Correct 179 ms 20392 KB Output is correct
7 Correct 198 ms 19960 KB Output is correct
8 Correct 195 ms 20108 KB Output is correct
9 Correct 195 ms 20212 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11000 KB Output is correct
2 Correct 36 ms 12024 KB Output is correct
3 Correct 156 ms 18820 KB Output is correct
4 Correct 244 ms 20708 KB Output is correct
5 Correct 243 ms 20788 KB Output is correct
6 Correct 235 ms 20692 KB Output is correct
7 Correct 244 ms 20728 KB Output is correct
8 Correct 240 ms 20672 KB Output is correct
9 Correct 312 ms 20744 KB Output is correct
10 Correct 258 ms 20772 KB Output is correct
11 Correct 255 ms 19996 KB Output is correct
12 Correct 260 ms 20400 KB Output is correct
13 Correct 233 ms 20648 KB Output is correct
14 Correct 255 ms 20032 KB Output is correct
15 Correct 216 ms 20864 KB Output is correct
16 Correct 228 ms 20712 KB Output is correct
17 Correct 274 ms 20368 KB Output is correct
18 Correct 271 ms 20148 KB Output is correct
19 Correct 250 ms 20820 KB Output is correct
20 Correct 259 ms 20112 KB Output is correct
21 Correct 205 ms 21688 KB Output is correct
22 Correct 209 ms 21696 KB Output is correct
23 Correct 229 ms 21172 KB Output is correct
24 Correct 199 ms 21088 KB Output is correct
25 Correct 258 ms 20752 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12092 KB Output is correct
2 Correct 41 ms 12144 KB Output is correct
3 Correct 283 ms 21392 KB Output is correct
4 Correct 323 ms 21916 KB Output is correct
5 Correct 358 ms 23108 KB Output is correct
6 Correct 377 ms 22924 KB Output is correct
7 Correct 383 ms 23256 KB Output is correct
8 Correct 336 ms 23244 KB Output is correct
9 Correct 285 ms 19244 KB Output is correct
10 Correct 292 ms 20048 KB Output is correct
11 Correct 302 ms 20656 KB Output is correct
12 Correct 356 ms 22168 KB Output is correct
13 Correct 393 ms 22884 KB Output is correct
14 Correct 395 ms 22924 KB Output is correct
15 Correct 389 ms 22916 KB Output is correct
16 Correct 308 ms 21052 KB Output is correct
17 Correct 202 ms 21708 KB Output is correct
18 Correct 218 ms 21928 KB Output is correct
19 Correct 197 ms 21672 KB Output is correct
20 Correct 215 ms 21920 KB Output is correct
21 Correct 348 ms 22760 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12092 KB Output is correct
2 Correct 32 ms 12152 KB Output is correct
3 Correct 310 ms 21212 KB Output is correct
4 Correct 297 ms 21580 KB Output is correct
5 Correct 300 ms 21920 KB Output is correct
6 Correct 385 ms 22820 KB Output is correct
7 Correct 279 ms 21156 KB Output is correct
8 Correct 304 ms 21596 KB Output is correct
9 Correct 330 ms 21792 KB Output is correct
10 Correct 376 ms 22972 KB Output is correct
11 Correct 399 ms 22968 KB Output is correct
12 Correct 382 ms 22956 KB Output is correct
13 Correct 303 ms 20176 KB Output is correct
14 Correct 277 ms 20024 KB Output is correct
15 Correct 293 ms 20240 KB Output is correct
16 Correct 251 ms 20044 KB Output is correct
17 Correct 315 ms 20340 KB Output is correct
18 Correct 239 ms 20016 KB Output is correct
19 Correct 381 ms 22132 KB Output is correct
20 Correct 412 ms 22628 KB Output is correct
21 Correct 382 ms 23232 KB Output is correct
22 Correct 331 ms 22908 KB Output is correct
23 Correct 421 ms 23344 KB Output is correct
24 Correct 392 ms 23324 KB Output is correct
25 Correct 362 ms 23000 KB Output is correct
26 Correct 372 ms 23008 KB Output is correct
27 Correct 232 ms 21912 KB Output is correct
28 Correct 256 ms 21564 KB Output is correct
29 Correct 231 ms 21924 KB Output is correct
30 Correct 227 ms 21716 KB Output is correct
31 Correct 229 ms 21664 KB Output is correct
32 Correct 233 ms 21544 KB Output is correct
33 Correct 260 ms 21968 KB Output is correct
34 Correct 232 ms 21972 KB Output is correct
35 Correct 219 ms 21792 KB Output is correct
36 Correct 231 ms 21492 KB Output is correct
37 Correct 239 ms 21840 KB Output is correct
38 Correct 227 ms 21740 KB Output is correct
39 Correct 359 ms 23196 KB Output is correct
40 Correct 369 ms 23140 KB Output is correct
41 Correct 348 ms 22828 KB Output is correct
42 Correct 398 ms 23144 KB Output is correct