oj.uz

Submission #823246

# Submission time Handle Problem Language Result Execution time Memory
823246 2023-08-12T09:58:13 Z Dremix10 Highway Tolls (IOI18_highway) C++17
12 / 100
 76 ms 15176 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

vector<vector<pi> > a(N);
vector<pi> pos;
vector<pi> par(N);

void dfs(int s, int e, int cur, int f){
    if(cur == f){
        pos.push_back({par[s].S,s});
        return;
    }
    for(auto x : a[s]){
        if(x.F == e)continue;
        par[x.F] = {s,x.S};
        dfs(x.F,s,cur+1,f);
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
    int i;

    int m = u.size();

    for(i=0;i<m;i++){
        a[v[i]].push_back({u[i],i});
        a[u[i]].push_back({v[i],i});
    }

    vector<int> w(m,0);

    ll d = ask(w);
    int dep = d/A;

    dfs(0,0,0,dep);
    assert(pos.size() > 0);
    int l = 0,r = pos.size() - 1;

    while(l < r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++){
            w[pos[i].F] = 1;
        }
        ll res = ask(w);
        for(i=0;i<=mid;i++){
            w[pos[i].F] = 0;
        }

        if(res != d){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    answer(0,pos[r].S);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 4 ms 9680 KB Output is correct
3 Correct 4 ms 9680 KB Output is correct
4 Correct 4 ms 9680 KB Output is correct
5 Correct 5 ms 9600 KB Output is correct
6 Correct 5 ms 9732 KB Output is correct
7 Correct 4 ms 9596 KB Output is correct
8 Correct 4 ms 9680 KB Output is correct
9 Correct 4 ms 9680 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 4 ms 9708 KB Output is correct
12 Correct 4 ms 9680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 10 ms 10192 KB Output is correct
3 Correct 67 ms 15056 KB Output is correct
4 Correct 69 ms 15072 KB Output is correct
5 Correct 75 ms 14936 KB Output is correct
6 Correct 64 ms 14876 KB Output is correct
7 Correct 64 ms 14928 KB Output is correct
8 Correct 76 ms 15048 KB Output is correct
9 Correct 60 ms 14848 KB Output is correct
10 Correct 66 ms 15036 KB Output is correct
11 Correct 66 ms 14836 KB Output is correct
12 Correct 62 ms 15028 KB Output is correct
13 Correct 59 ms 14920 KB Output is correct
14 Correct 62 ms 15176 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 10192 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 6 ms 9728 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 Incorrect 16 ms 11436 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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