oj.uz

Submission #137473

# Submission time Handle Problem Language Result Execution time Memory
137473 2019-07-27T23:21:15 Z Angelos Highway Tolls (IOI18_highway) C++11
51 / 100
 386 ms 31748 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 == 0) {}//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;

        bfo = (iss == 0) ? cur : bfo;
    }
    //cout << "wow " << lo << " " << u.size() << endl;
    return u[lo];
}

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



    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[70535] << " " << d1[1479] << endl;
    //cout << d2[70535] << " " << d2[1479] << 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<M; i++) w[i] = 0;
    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);

    for(int i=0; i<M; i++) w[i] = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<adj2[i].size(); j++) w[deg2[i][j]] = 1;
    for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
    ll assk2 = ask(w);

    int patu1 = (int)(((ll)assk1-assk)/((ll)B-A));
    int patv1 = dist - patu1 - 1;
    int patv2 = (int)(((ll)assk2-assk)/((ll)B-A));
    int patu2 = dist - patv2 - 1;

    int patu=patu1 , patv = patv1;

    if(patu1 != patu2){
        if(assk1 <= assk2) patu=patu1,patv=patv1;
        else patu=patu2,patv=patv2;
    }

    //cout << assk1 << " " << assk2 << " " << 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 bfs1(int, int)':
highway.cpp:65: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:82: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:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur1].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<adj[cur2].size(); i++){
                          ~^~~~~~~~~~~~~~~~~
highway.cpp:182: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:183:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<bad.size(); i++) w[bad[i]] = 1;
                  ~^~~~~~~~~~~
highway.cpp:188:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<adj2[i].size(); j++) w[deg2[i][j]] = 1;
                      ~^~~~~~~~~~~~~~~
highway.cpp:189: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 15 ms 13864 KB Output is correct
2 Correct 15 ms 13816 KB Output is correct
3 Correct 14 ms 13800 KB Output is correct
4 Correct 15 ms 13820 KB Output is correct
5 Correct 14 ms 13904 KB Output is correct
6 Correct 18 ms 13816 KB Output is correct
7 Correct 14 ms 13864 KB Output is correct
8 Correct 14 ms 13804 KB Output is correct
9 Correct 14 ms 13888 KB Output is correct
10 Correct 14 ms 13800 KB Output is correct
11 Correct 15 ms 13888 KB Output is correct
12 Correct 14 ms 13816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14072 KB Output is correct
2 Correct 32 ms 15664 KB Output is correct
3 Correct 339 ms 29992 KB Output is correct
4 Correct 330 ms 30004 KB Output is correct
5 Correct 322 ms 29996 KB Output is correct
6 Correct 324 ms 29972 KB Output is correct
7 Correct 313 ms 30008 KB Output is correct
8 Correct 330 ms 29996 KB Output is correct
9 Correct 323 ms 30020 KB Output is correct
10 Correct 320 ms 30008 KB Output is correct
11 Correct 332 ms 29540 KB Output is correct
12 Correct 310 ms 29556 KB Output is correct
13 Correct 315 ms 29584 KB Output is correct
14 Correct 331 ms 29572 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15608 KB Output is correct
2 Correct 61 ms 17468 KB Output is correct
3 Correct 82 ms 19044 KB Output is correct
4 Correct 215 ms 29536 KB Output is correct
5 Correct 193 ms 29540 KB Output is correct
6 Correct 215 ms 29544 KB Output is correct
7 Correct 200 ms 29596 KB Output is correct
8 Correct 202 ms 29544 KB Output is correct
9 Correct 224 ms 29552 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 15652 KB Output is correct
3 Correct 232 ms 26444 KB Output is correct
4 Correct 346 ms 30016 KB Output is correct
5 Correct 295 ms 29988 KB Output is correct
6 Correct 323 ms 29860 KB Output is correct
7 Correct 299 ms 29976 KB Output is correct
8 Correct 298 ms 29952 KB Output is correct
9 Correct 330 ms 29996 KB Output is correct
10 Correct 307 ms 30000 KB Output is correct
11 Correct 328 ms 29576 KB Output is correct
12 Correct 338 ms 29600 KB Output is correct
13 Correct 346 ms 29584 KB Output is correct
14 Correct 342 ms 29608 KB Output is correct
15 Correct 278 ms 30044 KB Output is correct
16 Correct 336 ms 29956 KB Output is correct
17 Correct 323 ms 29580 KB Output is correct
18 Correct 319 ms 29588 KB Output is correct
19 Correct 325 ms 30012 KB Output is correct
20 Correct 334 ms 29576 KB Output is correct
21 Correct 284 ms 31748 KB Output is correct
22 Correct 337 ms 31748 KB Output is correct
23 Correct 320 ms 31544 KB Output is correct
24 Correct 318 ms 31236 KB Output is correct
25 Correct 386 ms 29780 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 15644 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 45 ms 15628 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -