oj.uz

Submission #999570

# Submission time Handle Problem Language Result Execution time Memory
999570 2024-06-15T20:09:22 Z amine_aroua Highway Tolls (IOI18_highway) C++17
51 / 100
 181 ms 12164 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;
int n;
vector<pair<int ,int>> adj[MAXN];
vector<int> zeros , ones;
intt val;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int go(int root)
{
    vector<int> dist(n , n);
    vector<bool> vis(n , 0);
    dist[root] = 0;
    queue<int> q;
    q.push(root);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        if(vis[x])
            continue;
        vis[x] = 1;
        for(auto [u , i] : adj[x])
        {
            if(dist[u] > dist[x] + 1)
            {
                dist[u] = dist[x] + 1;
                q.push(u);
            }
        }
    }
    vector<pair<int ,int>> nds;
    fore(i , n)
        nds.pb({dist[i] , i});
    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) {
            for(auto i : adj[nds[j].second])asked[i.second] = 0;
        }
        if(ask(asked) == val)
            l = mid;
        else
            r = mid;
    }
    return nds[l].second;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    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});
    }
    int S = go(go(0));
    answer(S , go(S));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 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 1 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 14 ms 3416 KB Output is correct
3 Correct 155 ms 10180 KB Output is correct
4 Correct 137 ms 10152 KB Output is correct
5 Correct 151 ms 10168 KB Output is correct
6 Correct 134 ms 10280 KB Output is correct
7 Correct 159 ms 10168 KB Output is correct
8 Correct 151 ms 10164 KB Output is correct
9 Correct 149 ms 10176 KB Output is correct
10 Correct 134 ms 10164 KB Output is correct
11 Correct 142 ms 10044 KB Output is correct
12 Correct 149 ms 9572 KB Output is correct
13 Correct 143 ms 9808 KB Output is correct
14 Correct 122 ms 9588 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3336 KB Output is correct
2 Correct 18 ms 3980 KB Output is correct
3 Correct 33 ms 4780 KB Output is correct
4 Correct 87 ms 9584 KB Output is correct
5 Correct 86 ms 9516 KB Output is correct
6 Correct 78 ms 9592 KB Output is correct
7 Correct 95 ms 9652 KB Output is correct
8 Correct 103 ms 9584 KB Output is correct
9 Correct 98 ms 9520 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 16 ms 3432 KB Output is correct
3 Correct 116 ms 8720 KB Output is correct
4 Correct 148 ms 10164 KB Output is correct
5 Correct 135 ms 10164 KB Output is correct
6 Correct 143 ms 10168 KB Output is correct
7 Correct 141 ms 10160 KB Output is correct
8 Correct 155 ms 10160 KB Output is correct
9 Correct 132 ms 10280 KB Output is correct
10 Correct 154 ms 10172 KB Output is correct
11 Correct 141 ms 9576 KB Output is correct
12 Correct 125 ms 9584 KB Output is correct
13 Correct 135 ms 9820 KB Output is correct
14 Correct 139 ms 9584 KB Output is correct
15 Correct 151 ms 10172 KB Output is correct
16 Correct 135 ms 10300 KB Output is correct
17 Correct 149 ms 9588 KB Output is correct
18 Correct 142 ms 9784 KB Output is correct
19 Correct 172 ms 10380 KB Output is correct
20 Correct 125 ms 9744 KB Output is correct
21 Correct 93 ms 10580 KB Output is correct
22 Correct 116 ms 10420 KB Output is correct
23 Correct 116 ms 10812 KB Output is correct
24 Correct 107 ms 10320 KB Output is correct
25 Correct 114 ms 9828 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3416 KB Output is correct
2 Correct 15 ms 3512 KB Output is correct
3 Correct 143 ms 10572 KB Output is correct
4 Correct 163 ms 11252 KB Output is correct
5 Correct 181 ms 12164 KB Output is correct
6 Incorrect 168 ms 12092 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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