Submission #999398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
999398	2024-06-15T12:25:41 Z	amine_aroua	Highway Tolls (IOI18_highway)	C++17	6 / 100	76 ms	8072 KB

highway

#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;
vector<int> nodes;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dfs(int x , int p , intt val , intt dep)
{
    if(dep == (val/b))
    {
        nodes.pb(x);
        return;
    }
    for(auto [u , i] : adj[x])
    {
        if(u == p)
            continue;
        dfs(u , x , val ,dep + 1 );
    }
}
int findT(int S)
{
    intt val = ask(ones);
    dfs(0 , -1 , val , 0);
    int l = 0 , r = (int)nodes.size();
    vector<int> asked = ones;
    while(l + 1 < r)
    {
        int mid = (l + r)/2;
        asked = ones;
        forr(j , 0 , mid - 1) {
            for(auto [u , i] : adj[nodes[j]])
                asked[i] = 0;
        }
        if(ask(asked) == val)
            l = mid;
        else
            r = mid;
    }
    return nodes[l];
}
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 , N)adj[i].clear();
    fore(i , m)
    {
        adj[U[i]].pb({V[i] , i});
        adj[V[i]].pb({U[i] , i});
    }
//    answer(0 ,findT(0));
    int l = 0 , r = N;
    intt val = ask(ones);
    vector<int> asked = ones;
    while(l + 1 < r)
    {
        int mid = (l + r)/2;
        asked = ones;
        forr(j , 0 , mid - 1) {
            for(auto [u , i] : adj[j])
                asked[i] = 0;
        }
        if(ask(asked) == val)
            l = mid;
        else
            r = mid;
    }
    answer(l , l + (val/b));
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2904 KB	Output is correct
2	Correct	13 ms	3720 KB	Output is correct
3	Correct	25 ms	4184 KB	Output is correct
4	Correct	59 ms	8072 KB	Output is correct
5	Correct	57 ms	7844 KB	Output is correct
6	Correct	55 ms	8044 KB	Output is correct
7	Correct	60 ms	7740 KB	Output is correct
8	Correct	76 ms	7832 KB	Output is correct
9	Correct	61 ms	7740 KB	Output is correct