oj.uz

Submission #118793

# Submission time Handle Problem Language Result Execution time Memory
118793 2019-06-19T18:20:31 Z someone_aa Highway Tolls (IOI18_highway) C++17
51 / 100
 381 ms 23272 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=li;i<=mid;i++) {
            w[i] = 1;
        }
        ll distb = ask(w);
        for(int i=li;i<=mid;i++) {
            w[i] = 0;
        }

        if(dista == distb) {
            li = mid + 1;
        }
        else {
            ri = 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 10872 KB Output is correct
2 Correct 12 ms 10872 KB Output is correct
3 Correct 11 ms 10872 KB Output is correct
4 Correct 12 ms 10992 KB Output is correct
5 Correct 12 ms 10876 KB Output is correct
6 Correct 12 ms 10872 KB Output is correct
7 Correct 12 ms 10908 KB Output is correct
8 Correct 12 ms 10920 KB Output is correct
9 Correct 12 ms 10876 KB Output is correct
10 Correct 11 ms 11008 KB Output is correct
11 Correct 12 ms 10920 KB Output is correct
12 Correct 12 ms 10876 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 11996 KB Output is correct
3 Correct 248 ms 20724 KB Output is correct
4 Correct 262 ms 20732 KB Output is correct
5 Correct 241 ms 20724 KB Output is correct
6 Correct 245 ms 20712 KB Output is correct
7 Correct 251 ms 20740 KB Output is correct
8 Correct 250 ms 20712 KB Output is correct
9 Correct 243 ms 20752 KB Output is correct
10 Correct 275 ms 20712 KB Output is correct
11 Correct 289 ms 20228 KB Output is correct
12 Correct 279 ms 20288 KB Output is correct
13 Correct 261 ms 20040 KB Output is correct
14 Correct 262 ms 20376 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 52 ms 12948 KB Output is correct
3 Correct 66 ms 14016 KB Output is correct
4 Correct 201 ms 19964 KB Output is correct
5 Correct 188 ms 19952 KB Output is correct
6 Correct 180 ms 20376 KB Output is correct
7 Correct 188 ms 20040 KB Output is correct
8 Correct 171 ms 19996 KB Output is correct
9 Correct 165 ms 20212 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11000 KB Output is correct
2 Correct 32 ms 11996 KB Output is correct
3 Correct 209 ms 18828 KB Output is correct
4 Correct 249 ms 20672 KB Output is correct
5 Correct 251 ms 20716 KB Output is correct
6 Correct 272 ms 20696 KB Output is correct
7 Correct 238 ms 20752 KB Output is correct
8 Correct 269 ms 20696 KB Output is correct
9 Correct 249 ms 20700 KB Output is correct
10 Correct 225 ms 20752 KB Output is correct
11 Correct 247 ms 20000 KB Output is correct
12 Correct 282 ms 20376 KB Output is correct
13 Correct 270 ms 20624 KB Output is correct
14 Correct 256 ms 20036 KB Output is correct
15 Correct 231 ms 20640 KB Output is correct
16 Correct 246 ms 20720 KB Output is correct
17 Correct 248 ms 20416 KB Output is correct
18 Correct 281 ms 20096 KB Output is correct
19 Correct 250 ms 20760 KB Output is correct
20 Correct 256 ms 20108 KB Output is correct
21 Correct 189 ms 21724 KB Output is correct
22 Correct 211 ms 21696 KB Output is correct
23 Correct 237 ms 21176 KB Output is correct
24 Correct 234 ms 21080 KB Output is correct
25 Correct 253 ms 20656 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12084 KB Output is correct
2 Correct 40 ms 12152 KB Output is correct
3 Correct 278 ms 21444 KB Output is correct
4 Correct 316 ms 21980 KB Output is correct
5 Correct 381 ms 23272 KB Output is correct
6 Incorrect 357 ms 22880 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 12092 KB Output is correct
2 Correct 40 ms 12072 KB Output is correct
3 Correct 316 ms 21276 KB Output is correct
4 Incorrect 254 ms 21580 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -