oj.uz

Submission #76993

# Submission time Handle Problem Language Result Execution time Memory
76993 2018-09-19T20:30:58 Z someone_aa Highway Tolls (IOI18_highway) C++17
51 / 100
 264 ms 12464 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<pair<int,int> > g[maxn];

int dist[maxn][2], parent[maxn][2];
bool visited[maxn];

ll dista;

void bfs(int st, int d) {
    memset(visited,false,sizeof(visited));
    queue<int>q;
    q.push(st);

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

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

        for(auto i:g[curr]) {
            if(!visited[i.first]) {
                visited[i.first] = true;
                dist[i.first][d] = dist[curr][d] + 1;
                parent[i.first][d] = i.second;
                q.push(i.first);
            }
        }
    }
}

int solve(vector<int> x, int d) {
    vector<int>w;
    for(int i=0;i<m;i++) w.pb(0);
    vector<pair<int,int> > dists;
    for(int i:x) {
        dists.pb(mp(dist[i][d], i));
    }
    sort(dists.begin(), dists.end());

    //cout<<d<<": ";
    //for(int i:x) cout<<i<<" ";
    //cout<<"\n";
    for(int i=0;i<m;i++) w[i] = 1;
    for(int i:x) if(parent[i][d] != -1) w[parent[i][d]] = 0;

    /*cout<<d<<":\n";
    for(auto i:dists) {
        cout<<i.first<<" "<<i.second<<"\n";
    }*/

    ll dista = ask(w);
    int li=0, ri=dists.size()-1;
    while(li<ri) {
        int mid = (li+ri)/2;

        for(int i=mid+1;i<=ri;i++) {
            if(parent[dists[i].second][d] != -1)
                w[parent[dists[i].second][d]] = 1;
        }
        ll distb = ask(w);

        for(int i=mid+1;i<=ri;i++) {
            if(parent[dists[i].second][d] != -1)
                w[parent[dists[i].second][d]] = 0;
        }

        if(dista == distb) {
            ri = mid;
        }
        else {
            li = mid + 1;
        }
    }
    return dists[li].second;
}

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++) {
        g[U[i]].pb(mp(V[i], i));
        g[V[i]].pb(mp(U[i], i));
    }

    for(int i=0;i<m;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];
    bfs(u, 0);
    bfs(v, 1);

    vector<int>su, sv;
    for(int i=0;i<n;i++) {
        if(dist[i][0] <= dist[i][1]) {
            su.pb(i);
        }
        else {
            sv.pb(i);
        }
    }

    //cerr<<u<<" "<<v<<"\n";

    int xx = solve(su, 0);
    int yy = solve(sv, 1);
    //cout<<xx<<" "<<yy<<"\n";
    answer(xx, yy);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 4 ms 2728 KB Output is correct
6 Correct 4 ms 2728 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2684 KB Output is correct
9 Correct 4 ms 2728 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2940 KB Output is correct
2 Correct 27 ms 3752 KB Output is correct
3 Correct 224 ms 11552 KB Output is correct
4 Correct 222 ms 12128 KB Output is correct
5 Correct 215 ms 12136 KB Output is correct
6 Correct 218 ms 12128 KB Output is correct
7 Correct 223 ms 12136 KB Output is correct
8 Correct 218 ms 12148 KB Output is correct
9 Correct 209 ms 11536 KB Output is correct
10 Correct 217 ms 12264 KB Output is correct
11 Correct 219 ms 10632 KB Output is correct
12 Correct 253 ms 11364 KB Output is correct
13 Correct 201 ms 11556 KB Output is correct
14 Correct 245 ms 10936 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3752 KB Output is correct
2 Correct 43 ms 4604 KB Output is correct
3 Correct 59 ms 5464 KB Output is correct
4 Correct 204 ms 10684 KB Output is correct
5 Correct 177 ms 10692 KB Output is correct
6 Correct 171 ms 11392 KB Output is correct
7 Correct 164 ms 10976 KB Output is correct
8 Correct 180 ms 10876 KB Output is correct
9 Correct 162 ms 11236 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2856 KB Output is correct
2 Correct 28 ms 3696 KB Output is correct
3 Correct 159 ms 10352 KB Output is correct
4 Correct 195 ms 11888 KB Output is correct
5 Correct 213 ms 11508 KB Output is correct
6 Correct 215 ms 12144 KB Output is correct
7 Correct 200 ms 11540 KB Output is correct
8 Correct 236 ms 11452 KB Output is correct
9 Correct 207 ms 11536 KB Output is correct
10 Correct 226 ms 11460 KB Output is correct
11 Correct 243 ms 10908 KB Output is correct
12 Correct 232 ms 11436 KB Output is correct
13 Correct 233 ms 11368 KB Output is correct
14 Correct 242 ms 10408 KB Output is correct
15 Correct 212 ms 12144 KB Output is correct
16 Correct 191 ms 12140 KB Output is correct
17 Correct 230 ms 10968 KB Output is correct
18 Correct 236 ms 10928 KB Output is correct
19 Correct 215 ms 11532 KB Output is correct
20 Correct 264 ms 11492 KB Output is correct
21 Correct 180 ms 12448 KB Output is correct
22 Correct 182 ms 12464 KB Output is correct
23 Correct 222 ms 11472 KB Output is correct
24 Correct 195 ms 11296 KB Output is correct
25 Correct 246 ms 11120 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3732 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3728 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -