oj.uz

Submission #999369

# Submission time Handle Problem Language Result Execution time Memory
999369 2024-06-15T11:27:33 Z amine_aroua Highway Tolls (IOI18_highway) C++17
5 / 100
 104 ms 15736 KB 
#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
#define forr(i , x , y) for(int i = x; i <= y;i++)
#define fore(i , n) for(int i = 0 ; i < n;i++)
#define forn(i ,x , y) for(int i = x ; i >= y;i--)
long long ask(const vector<int> &w);
void answer(int s, int t);
const int MAXN = 90001;
intt a , b;
vector<pair<int ,int>> adj[MAXN];
vector<int> zeros , ones;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dfs(int x , int p , intt val , int dep)
{
    if(dep == (val/b))
        return x;
    vector<pair<int ,int>> v;
    for(auto [u , i] : adj[x])
    {
        if(u == p)
            continue;
        v.pb({u , i});
    }
    int sz = (int)v.size();
    shuffle(v.begin() , v.end() , rng);
    if((int)v.size() == 1)
    {
        return dfs(v[0].first , x , val , dep + 1);
    }
    int l = 0 , r = sz;
    vector<int> asked = ones;
    while(l + 1 < r)
    {
        int mid = (l + r)/2;
        asked = ones;
        forr(i , 0 , mid - 1)
            asked[v[i].second] = 0;
        if(ask(asked) == val)
            l = mid;
        else
            r = mid;
    }
    int nxt  = v[l].first;
    return dfs(nxt , x , val , dep + 1);
}
int findT(int S)
{
    intt val = ask(ones);
    return dfs(S , -1 , val ,0);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    a = A , b = B;
    int m = (int)U.size();
    zeros.assign(m , 0);
    ones.assign(m , 1);
    fore(i , m)
    {
        adj[U[i]].pb({V[i] , i});
        adj[V[i]].pb({U[i] , i});
    }
    answer(0 ,findT(0));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 8 ms 3416 KB Output is correct
3 Incorrect 104 ms 15736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2904 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 Runtime error 4 ms 4952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 6488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 6488 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -