제출 #137473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137473		Angelos	통행료 (IOI18_highway)	C++11	51 / 100	386 ms	31748 KiB

highway

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31