oj.uz

Submission #137270

# Submission time Handle Problem Language Result Execution time Memory
137270 2019-07-27T11:05:25 Z Angelos Highway Tolls (IOI18_highway) C++11
11 / 100
 339 ms 262148 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;
int toask[MAXM] , M , N , A , B , dpt[MAXN] , vis[MAXN];
vector<int> w;
vector< int > adj[MAXN] , deg[MAXN];
ll assk;
int toggle(int c){
    return (c==0)?1:0;
}

int bsearch(int arr[]){
    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");
    vis[cur] = 1;
    for(int i=0; i<adj[cur].size(); i++){
        if(adj[cur][i] != pr && vis[adj[cur][i]] == 0) {

            w[deg[cur][i]] = 1;
            dfs(adj[cur][i] , cur);
        }
    }
}

void dfs1(int cur , int pr , int cnt , int d){
    //cout << "dfs1 " << cur << " " << pr << " " << cnt << endl;
    dpt[cur] = d;
    for(int i=0; i<adj[cur].size(); i++)
        if(adj[cur][i] != pr) {
            if(cnt == 1) toask[deg[cur][i]] = 1;
            dfs1(adj[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;
    if(N == M) {answer(1,3);return;}
    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;
    dfs(U[edg] , V[edg]);
    ll assk1 = ask(w);

    int patu = (int)(assk1-assk)/(B-A);
    int patv = dist - patu - 1;

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

    int edgu = U[edg],edgv = V[edg] , s , t;
    if(patu != 0){
        memset(toask , 0 ,sizeof toask);
        dfs1(U[edg] , V[edg] , patu , 0);
        edgu = bsearch(toask);
        if(dpt[U[edgu]] > dpt[V[edgu]]) s = U[edgu];
        else s = V[edgu];
    }
    else s = U[edg];


    if(patv != 0){
        memset(toask , 0 , sizeof toask);
        dfs1(V[edg] , U[edg] , patv , 0);
        edgv = bsearch(toask);
        if(dpt[U[edgv]] > dpt[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:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[cur].size(); i++){
                  ~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void dfs1(int, int, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[cur].size(); i++)
                  ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4952 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 6 ms 4948 KB Output is correct
4 Correct 7 ms 5160 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4948 KB Output is correct
7 Correct 6 ms 5168 KB Output is correct
8 Correct 6 ms 5032 KB Output is correct
9 Correct 6 ms 4948 KB Output is correct
10 Correct 6 ms 5032 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 4952 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 28 ms 6056 KB Output is correct
3 Correct 238 ms 14256 KB Output is correct
4 Correct 232 ms 14356 KB Output is correct
5 Correct 239 ms 14248 KB Output is correct
6 Correct 229 ms 13904 KB Output is correct
7 Correct 234 ms 14248 KB Output is correct
8 Correct 232 ms 14248 KB Output is correct
9 Correct 243 ms 14288 KB Output is correct
10 Correct 228 ms 14196 KB Output is correct
11 Correct 253 ms 15396 KB Output is correct
12 Correct 249 ms 16388 KB Output is correct
13 Correct 239 ms 15776 KB Output is correct
14 Runtime error 272 ms 31844 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6648 KB Output is correct
2 Correct 46 ms 8252 KB Output is correct
3 Correct 54 ms 9080 KB Output is correct
4 Correct 177 ms 18028 KB Output is correct
5 Correct 179 ms 18120 KB Output is correct
6 Correct 170 ms 19256 KB Output is correct
7 Correct 184 ms 17632 KB Output is correct
8 Correct 151 ms 18560 KB Output is correct
9 Correct 152 ms 16748 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5156 KB Output is correct
2 Correct 29 ms 6056 KB Output is correct
3 Correct 153 ms 12064 KB Output is correct
4 Correct 226 ms 14004 KB Output is correct
5 Correct 241 ms 14196 KB Output is correct
6 Correct 230 ms 13836 KB Output is correct
7 Correct 244 ms 13912 KB Output is correct
8 Correct 245 ms 14228 KB Output is correct
9 Correct 274 ms 14264 KB Output is correct
10 Correct 236 ms 14248 KB Output is correct
11 Runtime error 239 ms 31084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 339 ms 262148 KB Execution killed with signal 9 (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 319 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -