oj.uz

Submission #118745

# Submission time Handle Problem Language Result Execution time Memory
118745 2019-06-19T15:40:42 Z someone_aa Highway Tolls (IOI18_highway) C++17
51 / 100
 377 ms 20464 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 = 100100;
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];
bool visited[maxn];

ll dista;

map<pair<int,int>, int> ind;
int type[maxn];
vector<pair<int,int> > sta, stb;

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;

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

        for(auto i:g[curr]) {
            int ni = i.first;
            int nind = i.second;
            if(visited[ni]) continue;
            visited[ni] = true;
            type[ni] = currtype;
            pind[ni] = nind;
            q.push(mp(ni, currtype));
        }
    }
}

int solve(int root, int d) {
    // build bfs tree
    memset(visited,false,sizeof(visited));
    //memset(parent,-1,sizeof(parent));

    vector<int>v, v2, vind;

    queue<int>q;
    q.push(root);

    visited[root] = true;
    parent[root][d] = -1;

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

        v.pb(parent[curr][d]);
        v2.pb(curr);
        vind.pb(pind[curr]);
        for(auto i:gs[curr]) {
            if(!visited[i] && type[i] == type[curr]) {
                visited[i] = true;
                parent[i][d] = curr;
                dist[i][d] = dist[curr][d] + 1;
                q.push(i);
            }
        }
    }

    if(v.size() == 1) return v2[0];
    // perform binary search

    for(int i=0;i<v.size();i++) {
        if(v[i] == -1) continue; // root
        int cind = vind[i];
        w[cind] = 1;
    }

    int li = 0, ri = v.size() - 1;

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

        // all before mid put them as low cost and other as high cost
        for(int i=0;i<=mid;i++) {
            if(v[i] == -1) continue; // root
            int cind = vind[i];
            w[cind] = 0;
        }

        ll cdist = ask(w);
        for(int i=0;i<=mid;i++) {
            if(v[i] == -1) continue; // root
            int cind = vind[i];
            w[cind] = 1;
        }

        if(cdist == dista) {
            ri = mid;
        }
        else {
            li = mid + 1;
        }
    }

    for(int i=0;i<v.size();i++) {
        if(v[i] == -1) continue; // root
        int cind = vind[i];
        w[cind] = 0;
    }

    return v2[li];
}

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;
        }
    }
    int x = li;
    int u = U[x], v = V[x];

    //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:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                 ~^~~~~~~~~
highway.cpp:119:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7388 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7432 KB Output is correct
6 Correct 9 ms 7464 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 8 ms 7388 KB Output is correct
10 Correct 7 ms 7544 KB Output is correct
11 Correct 8 ms 7392 KB Output is correct
12 Correct 8 ms 7480 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7548 KB Output is correct
2 Correct 31 ms 8824 KB Output is correct
3 Correct 263 ms 19476 KB Output is correct
4 Correct 271 ms 19172 KB Output is correct
5 Correct 211 ms 19164 KB Output is correct
6 Correct 266 ms 19432 KB Output is correct
7 Correct 274 ms 19216 KB Output is correct
8 Correct 227 ms 19212 KB Output is correct
9 Correct 256 ms 19168 KB Output is correct
10 Correct 273 ms 19128 KB Output is correct
11 Correct 292 ms 17960 KB Output is correct
12 Correct 289 ms 18628 KB Output is correct
13 Correct 261 ms 18788 KB Output is correct
14 Correct 281 ms 18696 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8824 KB Output is correct
2 Correct 40 ms 9904 KB Output is correct
3 Correct 67 ms 11112 KB Output is correct
4 Correct 199 ms 17820 KB Output is correct
5 Correct 176 ms 17812 KB Output is correct
6 Correct 171 ms 18344 KB Output is correct
7 Correct 182 ms 18736 KB Output is correct
8 Correct 184 ms 17628 KB Output is correct
9 Correct 155 ms 18584 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 34 ms 8744 KB Output is correct
3 Correct 184 ms 16872 KB Output is correct
4 Correct 234 ms 19164 KB Output is correct
5 Correct 214 ms 19164 KB Output is correct
6 Correct 235 ms 19152 KB Output is correct
7 Correct 226 ms 19164 KB Output is correct
8 Correct 224 ms 19096 KB Output is correct
9 Correct 258 ms 19200 KB Output is correct
10 Correct 267 ms 19168 KB Output is correct
11 Correct 239 ms 18740 KB Output is correct
12 Correct 272 ms 18660 KB Output is correct
13 Correct 282 ms 18600 KB Output is correct
14 Correct 295 ms 18016 KB Output is correct
15 Correct 232 ms 19216 KB Output is correct
16 Correct 237 ms 19164 KB Output is correct
17 Correct 302 ms 18700 KB Output is correct
18 Correct 306 ms 18744 KB Output is correct
19 Correct 229 ms 19164 KB Output is correct
20 Correct 255 ms 18712 KB Output is correct
21 Correct 204 ms 20212 KB Output is correct
22 Correct 219 ms 20296 KB Output is correct
23 Correct 241 ms 19164 KB Output is correct
24 Correct 205 ms 19160 KB Output is correct
25 Correct 251 ms 18820 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8744 KB Output is correct
2 Correct 40 ms 8824 KB Output is correct
3 Correct 276 ms 19520 KB Output is correct
4 Correct 301 ms 19912 KB Output is correct
5 Incorrect 377 ms 20464 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8692 KB Output is correct
2 Correct 39 ms 8824 KB Output is correct
3 Correct 299 ms 18972 KB Output is correct
4 Incorrect 322 ms 19724 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -