oj.uz

Submission #118765

# Submission time Handle Problem Language Result Execution time Memory
118765 2019-06-19T16:49:12 Z someone_aa Highway Tolls (IOI18_highway) C++17
51 / 100
 380 ms 34092 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;
bool important[maxn];

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;

            important[nind] = true;

            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;
    }

    for(int i=0;i<m;i++) {
        if(!important[i]) w[i] = 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;
    }

    for(int i=0;i<m;i++) {
        if(!important[i]) w[i] = 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];
    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:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                 ~^~~~~~~~~
highway.cpp:128: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 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 9 ms 7464 KB Output is correct
6 Correct 9 ms 7464 KB Output is correct
7 Correct 9 ms 7464 KB Output is correct
8 Correct 8 ms 7416 KB Output is correct
9 Correct 9 ms 7544 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7416 KB Output is correct
12 Correct 8 ms 7440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7656 KB Output is correct
2 Correct 27 ms 8800 KB Output is correct
3 Correct 264 ms 19644 KB Output is correct
4 Correct 271 ms 19296 KB Output is correct
5 Correct 267 ms 19304 KB Output is correct
6 Correct 272 ms 19544 KB Output is correct
7 Correct 322 ms 19272 KB Output is correct
8 Correct 264 ms 19296 KB Output is correct
9 Correct 243 ms 19288 KB Output is correct
10 Correct 237 ms 19296 KB Output is correct
11 Correct 304 ms 18048 KB Output is correct
12 Correct 303 ms 18696 KB Output is correct
13 Correct 298 ms 18916 KB Output is correct
14 Correct 282 ms 18796 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8824 KB Output is correct
2 Correct 47 ms 9840 KB Output is correct
3 Correct 103 ms 11176 KB Output is correct
4 Correct 171 ms 17916 KB Output is correct
5 Correct 191 ms 17900 KB Output is correct
6 Correct 200 ms 18428 KB Output is correct
7 Correct 177 ms 18816 KB Output is correct
8 Correct 168 ms 17720 KB Output is correct
9 Correct 160 ms 18672 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7672 KB Output is correct
2 Correct 34 ms 8696 KB Output is correct
3 Correct 182 ms 17016 KB Output is correct
4 Correct 254 ms 19296 KB Output is correct
5 Correct 267 ms 19224 KB Output is correct
6 Correct 248 ms 19284 KB Output is correct
7 Correct 249 ms 19296 KB Output is correct
8 Correct 252 ms 19284 KB Output is correct
9 Correct 268 ms 19292 KB Output is correct
10 Correct 265 ms 19324 KB Output is correct
11 Correct 278 ms 18832 KB Output is correct
12 Correct 278 ms 18744 KB Output is correct
13 Correct 268 ms 18696 KB Output is correct
14 Correct 276 ms 18100 KB Output is correct
15 Correct 261 ms 19288 KB Output is correct
16 Correct 241 ms 19300 KB Output is correct
17 Correct 287 ms 18796 KB Output is correct
18 Correct 284 ms 18892 KB Output is correct
19 Correct 256 ms 19300 KB Output is correct
20 Correct 260 ms 18784 KB Output is correct
21 Correct 209 ms 20296 KB Output is correct
22 Correct 227 ms 20288 KB Output is correct
23 Correct 220 ms 19252 KB Output is correct
24 Correct 252 ms 19188 KB Output is correct
25 Correct 297 ms 18924 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8808 KB Output is correct
2 Correct 29 ms 8848 KB Output is correct
3 Correct 319 ms 19644 KB Output is correct
4 Runtime error 380 ms 34092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8804 KB Output is correct
2 Correct 38 ms 8928 KB Output is correct
3 Runtime error 319 ms 33604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -