oj.uz

Submission #999430

# Submission time Handle Problem Language Result Execution time Memory
999430 2024-06-15T13:22:26 Z amine_aroua Highway Tolls (IOI18_highway) C++17
51 / 100
 157 ms 262144 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;
vector<int> nodes;
int up[MAXN];
vector<pair<int ,int>> nds;
intt val;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dfs(int x , int p  , intt dep)
{
    if(dep == (val/b))
    {
        nodes.pb(x);
        return;
    }
    for(auto [u , i] : adj[x])
    {
        if(u == p)
            continue;
        dfs(u , x ,dep + 1 );
    }
}
void dfs1(int x , int p , int dep)
{
    nds.pb({dep , x});
    for(auto u : adj[x])
    {
        if(u.first == p)
            continue;
        up[u.first] = u.second;
        dfs1(u.first , x , dep + 1);
    }
}
int findT(int S)
{
    dfs(S , -1  , 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();
    val = ask(ones);
    fore(i , m)
    {
        adj[U[i]].pb({V[i] , i});
        adj[V[i]].pb({U[i] , i});
    }
    dfs1(0 , -1 , 0);
    sort(nds.rbegin() , nds.rend());
    int l = 0 , r = (int)nds.size();
    vector<int> asked = ones;
    while(l + 1 < r)
    {
        int mid = (l + r)/2;
        asked = ones;
        forr(j , 0 , mid - 1) {
            asked[up[nds[j].second]] = 0;
        }
        if(ask(asked) == val)
            l = mid;
        else
            r = mid;
    }
    int S = nds[l].second;
    answer(S , findT(S));
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 11 ms 3560 KB Output is correct
3 Correct 90 ms 9908 KB Output is correct
4 Correct 80 ms 9852 KB Output is correct
5 Correct 87 ms 10344 KB Output is correct
6 Correct 85 ms 9836 KB Output is correct
7 Correct 102 ms 9916 KB Output is correct
8 Correct 100 ms 9808 KB Output is correct
9 Correct 95 ms 9900 KB Output is correct
10 Correct 93 ms 9856 KB Output is correct
11 Correct 82 ms 10952 KB Output is correct
12 Correct 93 ms 11680 KB Output is correct
13 Correct 80 ms 10980 KB Output is correct
14 Correct 77 ms 10664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4184 KB Output is correct
2 Correct 15 ms 5780 KB Output is correct
3 Correct 21 ms 7328 KB Output is correct
4 Correct 68 ms 16136 KB Output is correct
5 Correct 73 ms 16256 KB Output is correct
6 Correct 65 ms 16052 KB Output is correct
7 Correct 65 ms 16060 KB Output is correct
8 Correct 66 ms 16080 KB Output is correct
9 Correct 65 ms 16080 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 9 ms 3416 KB Output is correct
3 Correct 56 ms 8288 KB Output is correct
4 Correct 77 ms 9708 KB Output is correct
5 Correct 72 ms 9664 KB Output is correct
6 Correct 76 ms 9704 KB Output is correct
7 Correct 74 ms 9632 KB Output is correct
8 Correct 84 ms 9768 KB Output is correct
9 Correct 86 ms 9900 KB Output is correct
10 Correct 84 ms 9912 KB Output is correct
11 Correct 82 ms 10188 KB Output is correct
12 Correct 82 ms 11736 KB Output is correct
13 Correct 83 ms 11248 KB Output is correct
14 Correct 82 ms 11752 KB Output is correct
15 Correct 79 ms 9952 KB Output is correct
16 Correct 82 ms 9632 KB Output is correct
17 Correct 79 ms 11260 KB Output is correct
18 Correct 87 ms 10928 KB Output is correct
19 Correct 82 ms 9692 KB Output is correct
20 Correct 73 ms 12208 KB Output is correct
21 Correct 72 ms 10476 KB Output is correct
22 Correct 83 ms 10376 KB Output is correct
23 Correct 86 ms 10464 KB Output is correct
24 Correct 82 ms 11084 KB Output is correct
25 Correct 84 ms 15336 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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