oj.uz

Submission #137314

# Submission time Handle Problem Language Result Execution time Memory
137314 2019-07-27T12:46:35 Z Angelos Highway Tolls (IOI18_highway) C++11
51 / 100
 334 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)(((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 = 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 4948 KB Output is correct
2 Correct 6 ms 5036 KB Output is correct
3 Correct 6 ms 4952 KB Output is correct
4 Correct 6 ms 4960 KB Output is correct
5 Correct 6 ms 5160 KB Output is correct
6 Correct 7 ms 5036 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 4948 KB Output is correct
9 Correct 6 ms 4952 KB Output is correct
10 Correct 7 ms 4956 KB Output is correct
11 Correct 6 ms 4956 KB Output is correct
12 Correct 6 ms 4956 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5160 KB Output is correct
2 Correct 28 ms 6088 KB Output is correct
3 Correct 236 ms 14180 KB Output is correct
4 Correct 209 ms 14256 KB Output is correct
5 Correct 228 ms 14240 KB Output is correct
6 Correct 220 ms 13920 KB Output is correct
7 Correct 212 ms 14252 KB Output is correct
8 Correct 234 ms 14260 KB Output is correct
9 Correct 241 ms 14228 KB Output is correct
10 Correct 232 ms 14236 KB Output is correct
11 Correct 245 ms 15396 KB Output is correct
12 Correct 242 ms 16232 KB Output is correct
13 Correct 220 ms 15784 KB Output is correct
14 Correct 243 ms 15888 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6724 KB Output is correct
2 Correct 43 ms 8180 KB Output is correct
3 Correct 94 ms 9080 KB Output is correct
4 Correct 152 ms 18040 KB Output is correct
5 Correct 173 ms 18116 KB Output is correct
6 Correct 173 ms 19280 KB Output is correct
7 Correct 172 ms 17796 KB Output is correct
8 Correct 175 ms 18548 KB Output is correct
9 Correct 168 ms 16772 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5156 KB Output is correct
2 Correct 28 ms 6088 KB Output is correct
3 Correct 162 ms 12124 KB Output is correct
4 Correct 214 ms 13964 KB Output is correct
5 Correct 242 ms 14332 KB Output is correct
6 Correct 205 ms 13836 KB Output is correct
7 Correct 214 ms 13820 KB Output is correct
8 Correct 264 ms 14316 KB Output is correct
9 Correct 253 ms 14256 KB Output is correct
10 Correct 248 ms 14360 KB Output is correct
11 Correct 262 ms 15464 KB Output is correct
12 Correct 237 ms 16280 KB Output is correct
13 Correct 247 ms 16032 KB Output is correct
14 Correct 224 ms 15876 KB Output is correct
15 Correct 222 ms 13836 KB Output is correct
16 Correct 223 ms 13832 KB Output is correct
17 Correct 242 ms 15608 KB Output is correct
18 Correct 268 ms 15984 KB Output is correct
19 Correct 216 ms 14308 KB Output is correct
20 Correct 220 ms 16652 KB Output is correct
21 Correct 182 ms 14764 KB Output is correct
22 Correct 208 ms 15100 KB Output is correct
23 Correct 217 ms 14912 KB Output is correct
24 Correct 259 ms 15168 KB Output is correct
25 Correct 285 ms 20216 KB Output is correct

Subtask #5
0 / 18.0

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