oj.uz

Submission #137413

# Submission time Handle Problem Language Result Execution time Memory
137413 2019-07-27T17:05:47 Z Angelos Highway Tolls (IOI18_highway) C++11
51 / 100
 380 ms 35748 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[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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13480 KB Output is correct
2 Correct 15 ms 13548 KB Output is correct
3 Correct 14 ms 13544 KB Output is correct
4 Correct 14 ms 13544 KB Output is correct
5 Correct 14 ms 13480 KB Output is correct
6 Correct 14 ms 13560 KB Output is correct
7 Correct 14 ms 13548 KB Output is correct
8 Correct 14 ms 13480 KB Output is correct
9 Correct 14 ms 13432 KB Output is correct
10 Correct 13 ms 13548 KB Output is correct
11 Correct 13 ms 13564 KB Output is correct
12 Correct 14 ms 13540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13704 KB Output is correct
2 Correct 42 ms 15352 KB Output is correct
3 Correct 315 ms 29708 KB Output is correct
4 Correct 318 ms 29984 KB Output is correct
5 Correct 334 ms 29988 KB Output is correct
6 Correct 297 ms 29668 KB Output is correct
7 Correct 308 ms 29968 KB Output is correct
8 Correct 330 ms 29936 KB Output is correct
9 Correct 317 ms 29668 KB Output is correct
10 Correct 332 ms 29964 KB Output is correct
11 Correct 351 ms 30980 KB Output is correct
12 Correct 350 ms 31884 KB Output is correct
13 Correct 334 ms 31292 KB Output is correct
14 Correct 356 ms 31300 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15944 KB Output is correct
2 Correct 55 ms 18248 KB Output is correct
3 Correct 61 ms 19832 KB Output is correct
4 Correct 194 ms 33348 KB Output is correct
5 Correct 209 ms 33520 KB Output is correct
6 Correct 218 ms 34728 KB Output is correct
7 Correct 199 ms 32768 KB Output is correct
8 Correct 208 ms 33960 KB Output is correct
9 Correct 186 ms 32052 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13688 KB Output is correct
2 Correct 48 ms 15308 KB Output is correct
3 Correct 258 ms 26148 KB Output is correct
4 Correct 326 ms 29696 KB Output is correct
5 Correct 324 ms 29608 KB Output is correct
6 Correct 349 ms 29612 KB Output is correct
7 Correct 345 ms 29220 KB Output is correct
8 Correct 309 ms 29548 KB Output is correct
9 Correct 343 ms 29964 KB Output is correct
10 Correct 322 ms 29960 KB Output is correct
11 Correct 344 ms 30924 KB Output is correct
12 Correct 329 ms 31788 KB Output is correct
13 Correct 322 ms 31556 KB Output is correct
14 Correct 354 ms 31292 KB Output is correct
15 Correct 304 ms 29600 KB Output is correct
16 Correct 339 ms 29580 KB Output is correct
17 Correct 380 ms 31136 KB Output is correct
18 Correct 365 ms 31540 KB Output is correct
19 Correct 338 ms 29628 KB Output is correct
20 Correct 325 ms 32168 KB Output is correct
21 Correct 277 ms 31132 KB Output is correct
22 Correct 274 ms 31016 KB Output is correct
23 Correct 290 ms 31240 KB Output is correct
24 Correct 321 ms 31344 KB Output is correct
25 Correct 367 ms 35748 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 29492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 29704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -