oj.uz

Submission #431577

# Submission time Handle Problem Language Result Execution time Memory
431577 2021-06-17T13:12:59 Z AmineWeslati Highway Tolls (IOI18_highway) C++14
12 / 100
 314 ms 86368 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define all(x) begin(x),end(x)
#define sz(v) (int)v.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//------------------------------------------

const int MX=2e5;

int N,M,A,B;
vi adj[MX];
unordered_map<int,int>mp[MX];

ll len; 


vi depth[MX],par(MX);
void dfs(int u=0, int p=0, int dep=0){
    depth[dep].pb(u);
    par[u]=p;
    for(int v: adj[u]) if(v!=p){
        dfs(v,u,dep+1);
    }
}

vi v; 
bool check(int l, int r){
    vi vec(M,0);
    FOR(i,l,r+1) vec[ mp[v[i]][par[v[i]]] ]=1;
    return ask(vec)>len*A;
}

void find_pair(int N, vi U, vi V, int A, int B) {
    ::N=N; ::A=A; ::B=B; 
    M=sz(U);
    FOR(i,0,M){
        int u=U[i],v=V[i];
        adj[u].pb(v);
        adj[v].pb(u);

        mp[u][v]=i; mp[v][u]=i;
    }

    vi vec;
    vec.assign(M,0);
    len=ask(vec); len/=A; 


    dfs();

    v=depth[len];

    int l=0,r=sz(v)-1,ans=-1;
    while(l<=r){
        int m=(l+r)/2;

        if(check(l,m)){
            ans=v[m];
            r=m-1;
        }
        else l=m+1;
    }
    answer(0,ans);
}

/*

4 3 1 3 0 3
0 1
0 2
0 3

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21448 KB Output is correct
2 Correct 17 ms 21408 KB Output is correct
3 Correct 17 ms 21388 KB Output is correct
4 Correct 17 ms 21444 KB Output is correct
5 Correct 18 ms 21404 KB Output is correct
6 Correct 17 ms 21364 KB Output is correct
7 Correct 16 ms 21412 KB Output is correct
8 Correct 18 ms 21448 KB Output is correct
9 Correct 17 ms 21460 KB Output is correct
10 Correct 17 ms 21468 KB Output is correct
11 Correct 16 ms 21456 KB Output is correct
12 Correct 15 ms 21448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 21576 KB Output is correct
2 Correct 40 ms 23644 KB Output is correct
3 Correct 293 ms 42480 KB Output is correct
4 Correct 300 ms 42512 KB Output is correct
5 Correct 314 ms 42520 KB Output is correct
6 Correct 288 ms 42456 KB Output is correct
7 Correct 286 ms 42528 KB Output is correct
8 Correct 310 ms 42556 KB Output is correct
9 Correct 291 ms 42548 KB Output is correct
10 Correct 302 ms 42560 KB Output is correct
11 Correct 283 ms 44044 KB Output is correct
12 Correct 296 ms 44972 KB Output is correct
13 Correct 299 ms 44256 KB Output is correct
14 Correct 301 ms 43572 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 24580 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 21660 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 86356 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 86368 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -