Submission #137413

#	Time	Username	Problem	Language	Result	Execution time	Memory
137413		Angelos	Highway Tolls (IOI18_highway)	C++11	51 / 100	380 ms	35748 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[MAXN] , d2[MAXN];
vector<int> w;
vector< int > adj[MAXN] , adj1[MAXN] , adj2[MAXN] , deg1[MAXN] , deg2[MAXN] , deg[MAXN];
ll assk;
int toggle(int c){
    return (c==0)?1:0;
}

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

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

    int lo = 0 , hi = u.size()-1;

    while(lo < hi){
        //cout << lo << " " << hi << endl;
        int mid = (lo+hi)/2;
        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 = cur;
    }
    //cout << "wow " << lo << " " << u.size() << endl;
    return u[lo];
}

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

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

void dfs1(int cur , int pr , int cnt , int d){
    //cout << "dfs1 " << cur << " " << pr << " " << cnt << endl;
    dpt1[cur] = d;
    for(int i=0; i<adj1[cur].size(); i++)
        if(adj1[cur][i] != pr) {
            if(cnt == 1) toask[deg1[cur][i]] = 1;
            dfs1(adj1[cur][i] , cur , cnt-1 , d+1);
        }
}

void dfs2(int cur , int pr , int cnt , int d){
    //cout << "dfs2 " << cur << " " << pr << " " << cnt << endl;
    dpt2[cur] = d;
    for(int i=0; i<adj2[cur].size(); i++)
        if(adj2[cur][i] != pr) {
            if(cnt == 1) toask[deg2[cur][i]] = 1;
            dfs2(adj2[cur][i] , cur , cnt-1 , d+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);

    int dist = (int)(assk/(ll)A);

    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;

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


    while(!q1.empty() || !q2.empty()){
        pii t1 = q1.front() , t2 = q2.front();q1.pop() , q2.pop();
        int cur1 = t1.first , cur2 = t2.first;
        v1[cur1] = v2[cur2] = 1;

        d1[cur1] = t1.second;
        d2[cur2] = t2.second;

        for(int i=0; i<adj[cur1].size(); i++){
            if(v1[adj[cur1][i]] == 0) q1.push({adj[cur1][i],t1.second+1});
        }

        for(int i=0; i<adj[cur2].size(); i++){
            if(v2[adj[cur2][i]] == 0) q2.push({adj[cur2][i],t2.second+1});
        }
    }



    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]]) {
            //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]]) {
            //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);
        }
    }

    dfs(U[edg] , -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);
        dfs1(U[edg] , -1 , patu , 0);
        edgu = bsearch(toask);
        if(dpt1[U[edgu]] > dpt1[V[edgu]]) s = U[edgu];
        else s = V[edgu];
    }
    else s = U[edg];


    if(patv != 0){
        memset(toask , 0 , sizeof toask);
        dfs2(V[edg] , -1 , patv , 0);
        edgv = bsearch(toask);
        if(dpt2[U[edgv]] > dpt2[V[edgv]]) t = U[edgv];
        else t = V[edgv];
    }
    else t = V[edg];
    //cout << edgu << " " << edgv << endl;



    answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:50: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 dfs1(int, int, int, int)':
highway.cpp:62: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 dfs2(int, int, int, int)':
highway.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj2[cur].size(); i++)
                  ~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj[cur1].size(); i++){
                      ~^~~~~~~~~~~~~~~~~
highway.cpp:119:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<adj[cur2].size(); i++){
                      ~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31