oj.uz

Submission #137466

# Submission time Handle Problem Language Result Execution time Memory
137466 2019-07-27T22:15:26 Z Angelos Highway Tolls (IOI18_highway) C++11
51 / 100
 431 ms 31736 KB 
#include "highway.h"
#include <bits/stdc++.h>
#include <vector>
#include <string.h>
#define pb push_back
#define MAXM 130100
#define MAXN 90100

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int toask[MAXM] , M , N , A , B , dpt2[MAXN] , dpt1[MAXN] , vis[MAXN];
int v1[MAXN] , v2[MAXN] , d1[MAXM] , d2[MAXM] , iss , dist;
vector<int> w,bad;
vector< int > adj[MAXN] , adj1[MAXN] , adj2[MAXN] , deg1[MAXN] , deg2[MAXN] , deg[MAXN];
queue <pii> q1 , q2;
ll assk;
int toggle(int c){
    return (c==0)?1:0;
}

int bsearch(int arr[]){
    //cout << "cool" << endl;
    vector<int>u,val,ori,ori1;val.clear(); u.clear();

    for(int i=0; i<M; i++){
        val.pb(0);
        if(arr[i] == 1) {u.pb(i);}
    }


    ll bfo = (iss==1) ? (ll)dist*B:assk;
    int lo = 0 , hi = u.size()-1;

    ori.resize(M,0);
    ori1.resize(M,1);
    while(lo < hi){
        //cout << lo << " " << hi << endl;
        int mid = (lo+hi)/2;

        if(iss != 1) val= ori;
        else val = ori1;

        for(int i=lo; i<=mid; i++) val[u[i]] = toggle(val[u[i]]);


        ll cur = ask(val);
        if(cur == bfo) lo = mid + 1;
        else hi = mid;
    }
    //cout << "wow " << lo << " " << u.size() << endl;
    return u[lo];
}

void dfs(int cur , int pr){
    //cout << cur << " " << "D" <<endl;
    //system("PAUSE");
    vis[cur] = 1;
    for(int i=0; i<adj1[cur].size(); i++){
        if(vis[adj1[cur][i]] == 0) {

            w[deg1[cur][i]] = 1;
            dfs(adj1[cur][i] , cur);
        }
    }
}

void bfs1(int cur , int d){
    queue <pii> q; q.push({cur,0});

    while(!q.empty()){
        pii tp = q.front();q.pop();

        int node = tp.first , dst = tp.second;
        vis[node] = 1;

        for(int i=0; i<adj1[node].size(); i++)
            if(vis[adj1[node][i]] == 0){
                q.push({adj1[node][i] , dst+1});
                if(dst == d-1) toask[deg1[node][i]] = 1;
            }
    }
}

void bfs2(int cur , int d){
    queue <pii> q; q.push({cur,0});

    while(!q.empty()){
        pii tp = q.front();q.pop();

        int node = tp.first , dst = tp.second;
        vis[node] = 1;

        for(int i=0; i<adj2[node].size(); i++)
            if(vis[adj2[node][i]] == 0){
                q.push({adj2[node][i] , dst+1});
                if(dst == d-1) toask[deg2[node][i]] = 1;
            }
    }
}

void find_pair(int n , vector<int> U , vector<int> V , int a , int b){
    M = U.size();N = n;A = a;B=b;

    for(int i=0; i<M; i++){
        adj[U[i]].pb(V[i]);
        adj[V[i]].pb(U[i]);

        deg[U[i]].pb(i);
        deg[V[i]].pb(i);
    }

    w.resize(M , 0);
    assk = ask(w);

    dist = (int)(assk/(ll)A);
    //cout << assk << endl;

    memset(toask , 0 ,sizeof toask);
    for(int i=0; i<M; i++)  toask[i] = 1;


    int edg = bsearch(toask);

    for(int i=0; i<M; i++) w[i] = 0;

    q1.push({U[edg],0});q2.push({V[edg],0});


    while(!q1.empty() || !q2.empty()){
        //cout << q1.size() << " " << q2.size() << endl;

        if(!q1.empty()){
            pii t1 = q1.front();q1.pop();
            int cur1 = t1.first;
            v1[cur1] = 1;
            d1[cur1] = t1.second;
            //if(cur1 == 9396 || cur1 == 4410) cout << t1.second << " C" <<endl;
            for(int i=0; i<adj[cur1].size(); i++){
                if(v1[adj[cur1][i]] == 0) {
                    q1.push({adj[cur1][i],t1.second+1});
                }
            }
        }

        if(!q2.empty()){
            pii t2 = q2.front();q2.pop();
            int cur2 = t2.first;
            //if(cur2 == 9396 || cur2 == 4410) cout << t2.second << " C" <<endl;
            v2[cur2] = 1;
            d2[cur2] = t2.second;
            for(int i=0; i<adj[cur2].size(); i++){
                if(v2[adj[cur2][i]] == 0) {
                    q2.push({adj[cur2][i],t2.second+1});

                }
            }
        }
    }

    //cout << d1[4410] << " " << d1[9396] << endl;
    //cout << d2[4410] << " " << d2[9396] << endl;

    //cout << "cool2" << endl;


    for(int i=0; i<M; i++){
        //cout << i << " " << d1[U[i]] << " " << d1[V[i]] << " " << d2[U[i]] << " " << d2[V[i]] << endl;
        if(d1[U[i]] < d2[U[i]] && d1[V[i]] < d2[V[i]]) {
            //f(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "1 : " << i << endl;
            adj1[U[i]].pb(V[i]);
            adj1[V[i]].pb(U[i]);

            deg1[U[i]].pb(i);
            deg1[V[i]].pb(i);
        }
        else if(d1[U[i]] > d2[U[i]] && d1[V[i]] > d2[V[i]]) {
            //if(U[i] == 4410 || V[i] == 4410 || U[i] == 9396 || V[i] == 9396)cout << "2 : " << i << endl;
            adj2[U[i]].pb(V[i]);
            adj2[V[i]].pb(U[i]);

            deg2[U[i]].pb(i);
            deg2[V[i]].pb(i);
        }
        else{
            if(i != edg)bad.push_back(i);
        }
    }



    for(int i=0; i<N; i++)
        for(int j=0; j<adj1[i].size(); j++) w[deg1[i][j]] = 1;
    for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
    ll assk1 = ask(w);
    int patu = (int)(((ll)assk1-assk)/((ll)B-A));
    int patv = dist - patu - 1;

    //cout << assk1 << " " << assk << " " << edg << " " << U[edg] << " " << V[edg] << " " << dist << " " << patu << " " << patv << endl;

    int edgu ,edgv  , s , t;
    if(patu != 0){
        memset(toask , 0 ,sizeof toask);
        //for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1;
        memset(vis , 0 ,sizeof vis);
        bfs1(U[edg] , patu);
        iss = 1;
        edgu = bsearch(toask);
        if(d1[U[edgu]] > d1[V[edgu]]) s = U[edgu];
        else s = V[edgu];
    }
    else s = U[edg];


    if(patv != 0){
        memset(toask , 0 , sizeof toask);
        //for(int i=0; i<bad.size(); i++) toask[bad[i]] = 1;
        memset(vis , 0 ,sizeof vis);
        bfs2(V[edg] , patv);
        edgv = bsearch(toask);
        if(d2[U[edgv]] > d2[V[edgv]]) t = U[edgv];
        else t = V[edgv];
    }
    else t = V[edg];
    //cout << s << " " << t << endl;



    answer(s,t);
}

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj1[cur].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void bfs1(int, int)':
highway.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj1[node].size(); i++)
                      ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void bfs2(int, int)':
highway.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj2[node].size(); i++)
                      ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:139:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur1].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:152:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur2].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:193:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<adj1[i].size(); j++) w[deg1[i][j]] = 1;
                      ~^~~~~~~~~~~~~~~
highway.cpp:194:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
                  ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13816 KB Output is correct
2 Correct 15 ms 13888 KB Output is correct
3 Correct 15 ms 13816 KB Output is correct
4 Correct 15 ms 13864 KB Output is correct
5 Correct 14 ms 13804 KB Output is correct
6 Correct 14 ms 13804 KB Output is correct
7 Correct 15 ms 13864 KB Output is correct
8 Correct 15 ms 13864 KB Output is correct
9 Correct 14 ms 13884 KB Output is correct
10 Correct 15 ms 13816 KB Output is correct
11 Correct 15 ms 13816 KB Output is correct
12 Correct 14 ms 13804 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14072 KB Output is correct
2 Correct 37 ms 15692 KB Output is correct
3 Correct 306 ms 30032 KB Output is correct
4 Correct 322 ms 29992 KB Output is correct
5 Correct 332 ms 30008 KB Output is correct
6 Correct 348 ms 29992 KB Output is correct
7 Correct 397 ms 30004 KB Output is correct
8 Correct 330 ms 30028 KB Output is correct
9 Correct 315 ms 29996 KB Output is correct
10 Correct 315 ms 29992 KB Output is correct
11 Correct 326 ms 29536 KB Output is correct
12 Correct 342 ms 29568 KB Output is correct
13 Correct 329 ms 29672 KB Output is correct
14 Correct 330 ms 29568 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15628 KB Output is correct
2 Correct 54 ms 17352 KB Output is correct
3 Correct 78 ms 19032 KB Output is correct
4 Correct 195 ms 29484 KB Output is correct
5 Correct 195 ms 29488 KB Output is correct
6 Correct 207 ms 29548 KB Output is correct
7 Correct 204 ms 29484 KB Output is correct
8 Correct 207 ms 29484 KB Output is correct
9 Correct 211 ms 29468 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13992 KB Output is correct
2 Correct 42 ms 15716 KB Output is correct
3 Correct 237 ms 26400 KB Output is correct
4 Correct 376 ms 30000 KB Output is correct
5 Correct 386 ms 29968 KB Output is correct
6 Correct 277 ms 29848 KB Output is correct
7 Correct 294 ms 29956 KB Output is correct
8 Correct 276 ms 29964 KB Output is correct
9 Correct 338 ms 29988 KB Output is correct
10 Correct 321 ms 30008 KB Output is correct
11 Correct 329 ms 29580 KB Output is correct
12 Correct 325 ms 29516 KB Output is correct
13 Correct 328 ms 29580 KB Output is correct
14 Correct 340 ms 29600 KB Output is correct
15 Correct 325 ms 29976 KB Output is correct
16 Correct 308 ms 29952 KB Output is correct
17 Correct 327 ms 29584 KB Output is correct
18 Correct 337 ms 29580 KB Output is correct
19 Correct 308 ms 30012 KB Output is correct
20 Correct 339 ms 29528 KB Output is correct
21 Correct 257 ms 31732 KB Output is correct
22 Correct 269 ms 31736 KB Output is correct
23 Correct 302 ms 31544 KB Output is correct
24 Correct 319 ms 31296 KB Output is correct
25 Correct 387 ms 29784 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15684 KB Output is correct
2 Correct 39 ms 15752 KB Output is correct
3 Correct 352 ms 30684 KB Output is correct
4 Incorrect 431 ms 29928 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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