oj.uz

Submission #118770

# Submission time Handle Problem Language Result Execution time Memory
118770 2019-06-19T17:22:45 Z someone_aa Highway Tolls (IOI18_highway) C++17
51 / 100
 382 ms 23260 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;

    //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 12 ms 10872 KB Output is correct
2 Correct 12 ms 10872 KB Output is correct
3 Correct 12 ms 10916 KB Output is correct
4 Correct 12 ms 11000 KB Output is correct
5 Correct 11 ms 10888 KB Output is correct
6 Correct 11 ms 10872 KB Output is correct
7 Correct 12 ms 10904 KB Output is correct
8 Correct 11 ms 10872 KB Output is correct
9 Correct 13 ms 10796 KB Output is correct
10 Correct 11 ms 10992 KB Output is correct
11 Correct 19 ms 10872 KB Output is correct
12 Correct 12 ms 10908 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10984 KB Output is correct
2 Correct 36 ms 11996 KB Output is correct
3 Correct 248 ms 20712 KB Output is correct
4 Correct 238 ms 20732 KB Output is correct
5 Correct 244 ms 20716 KB Output is correct
6 Correct 256 ms 20700 KB Output is correct
7 Correct 269 ms 20728 KB Output is correct
8 Correct 236 ms 20724 KB Output is correct
9 Correct 258 ms 20768 KB Output is correct
10 Correct 238 ms 20700 KB Output is correct
11 Correct 239 ms 20144 KB Output is correct
12 Correct 268 ms 20168 KB Output is correct
13 Correct 263 ms 19996 KB Output is correct
14 Correct 261 ms 20376 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11992 KB Output is correct
2 Correct 50 ms 12992 KB Output is correct
3 Correct 63 ms 14016 KB Output is correct
4 Correct 202 ms 19968 KB Output is correct
5 Correct 179 ms 19976 KB Output is correct
6 Correct 193 ms 20372 KB Output is correct
7 Correct 218 ms 19940 KB Output is correct
8 Correct 148 ms 20000 KB Output is correct
9 Correct 191 ms 20204 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11000 KB Output is correct
2 Correct 32 ms 11996 KB Output is correct
3 Correct 193 ms 18888 KB Output is correct
4 Correct 212 ms 20788 KB Output is correct
5 Correct 283 ms 20696 KB Output is correct
6 Correct 213 ms 20612 KB Output is correct
7 Correct 236 ms 20720 KB Output is correct
8 Correct 225 ms 20672 KB Output is correct
9 Correct 245 ms 20740 KB Output is correct
10 Correct 251 ms 20752 KB Output is correct
11 Correct 255 ms 19976 KB Output is correct
12 Correct 258 ms 20376 KB Output is correct
13 Correct 249 ms 20636 KB Output is correct
14 Correct 245 ms 20048 KB Output is correct
15 Correct 258 ms 20740 KB Output is correct
16 Correct 244 ms 20732 KB Output is correct
17 Correct 236 ms 20380 KB Output is correct
18 Correct 270 ms 20016 KB Output is correct
19 Correct 270 ms 20688 KB Output is correct
20 Correct 246 ms 20096 KB Output is correct
21 Correct 216 ms 21672 KB Output is correct
22 Correct 205 ms 21684 KB Output is correct
23 Correct 248 ms 21172 KB Output is correct
24 Correct 244 ms 21072 KB Output is correct
25 Correct 235 ms 20644 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11996 KB Output is correct
2 Correct 40 ms 12128 KB Output is correct
3 Correct 274 ms 21384 KB Output is correct
4 Correct 359 ms 21916 KB Output is correct
5 Correct 382 ms 23260 KB Output is correct
6 Incorrect 330 ms 22876 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 34 ms 12112 KB Output is correct
2 Correct 41 ms 12132 KB Output is correct
3 Correct 287 ms 21380 KB Output is correct
4 Incorrect 265 ms 21568 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -