oj.uz

Submission #999580

# Submission time Handle Problem Language Result Execution time Memory
999580 2024-06-15T20:31:18 Z amine_aroua Highway Tolls (IOI18_highway) C++17
90 / 100
 226 ms 39200 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());
map<vector<int> , intt> mp;
intt myask(vector<int> v)
{
    if(mp.count(v))
        return mp[v];
    return mp[v] = ask(v);
}
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 = zeros;
        forr(j , 0 , mid - 1) {
            for(auto i : adj[nds[j].second])asked[i.second] = 1;
        }
        if(myask(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 = myask(zeros);
    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 1 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 2720 KB Output is correct
2 Correct 15 ms 4440 KB Output is correct
3 Correct 158 ms 22264 KB Output is correct
4 Correct 132 ms 22496 KB Output is correct
5 Correct 146 ms 22536 KB Output is correct
6 Correct 123 ms 23092 KB Output is correct
7 Correct 151 ms 22468 KB Output is correct
8 Correct 155 ms 22136 KB Output is correct
9 Correct 150 ms 22316 KB Output is correct
10 Correct 153 ms 22532 KB Output is correct
11 Correct 141 ms 22760 KB Output is correct
12 Correct 145 ms 22688 KB Output is correct
13 Correct 144 ms 22596 KB Output is correct
14 Correct 132 ms 21964 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4924 KB Output is correct
2 Correct 21 ms 7368 KB Output is correct
3 Correct 37 ms 10104 KB Output is correct
4 Correct 112 ms 27788 KB Output is correct
5 Correct 116 ms 27920 KB Output is correct
6 Correct 95 ms 22436 KB Output is correct
7 Correct 124 ms 25984 KB Output is correct
8 Correct 102 ms 22564 KB Output is correct
9 Correct 114 ms 27000 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 14 ms 4440 KB Output is correct
3 Correct 122 ms 20960 KB Output is correct
4 Correct 153 ms 28636 KB Output is correct
5 Correct 153 ms 26880 KB Output is correct
6 Correct 168 ms 26524 KB Output is correct
7 Correct 149 ms 23728 KB Output is correct
8 Correct 154 ms 25580 KB Output is correct
9 Correct 142 ms 28644 KB Output is correct
10 Correct 173 ms 27900 KB Output is correct
11 Correct 145 ms 27580 KB Output is correct
12 Correct 129 ms 22676 KB Output is correct
13 Correct 139 ms 27544 KB Output is correct
14 Correct 149 ms 27728 KB Output is correct
15 Correct 172 ms 27564 KB Output is correct
16 Correct 154 ms 24760 KB Output is correct
17 Correct 148 ms 22620 KB Output is correct
18 Correct 142 ms 27212 KB Output is correct
19 Correct 174 ms 25752 KB Output is correct
20 Correct 140 ms 27520 KB Output is correct
21 Correct 99 ms 22796 KB Output is correct
22 Correct 99 ms 23172 KB Output is correct
23 Correct 116 ms 22728 KB Output is correct
24 Correct 103 ms 22116 KB Output is correct
25 Correct 119 ms 21784 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5120 KB Output is correct
2 Correct 16 ms 5308 KB Output is correct
3 Correct 160 ms 30244 KB Output is correct
4 Correct 178 ms 33256 KB Output is correct
5 Correct 226 ms 37852 KB Output is correct
6 Correct 187 ms 38436 KB Output is correct
7 Correct 204 ms 38904 KB Output is correct
8 Correct 179 ms 39200 KB Output is correct
9 Correct 139 ms 32504 KB Output is correct
10 Correct 127 ms 34844 KB Output is correct
11 Correct 118 ms 28628 KB Output is correct
12 Correct 175 ms 37080 KB Output is correct
13 Correct 177 ms 37276 KB Output is correct
14 Correct 187 ms 38028 KB Output is correct
15 Correct 178 ms 38552 KB Output is correct
16 Correct 169 ms 34944 KB Output is correct
17 Correct 110 ms 28308 KB Output is correct
18 Correct 128 ms 29112 KB Output is correct
19 Correct 127 ms 23312 KB Output is correct
20 Correct 131 ms 28896 KB Output is correct
21 Correct 216 ms 36788 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5128 KB Output is correct
2 Correct 14 ms 5364 KB Output is correct
3 Correct 183 ms 29988 KB Output is correct
4 Correct 162 ms 31544 KB Output is correct
5 Correct 177 ms 32512 KB Output is correct
6 Partially correct 180 ms 38520 KB Output is partially correct
7 Partially correct 159 ms 30832 KB Output is partially correct
8 Correct 165 ms 31512 KB Output is correct
9 Partially correct 171 ms 33624 KB Output is partially correct
10 Correct 199 ms 37844 KB Output is correct
11 Partially correct 203 ms 38900 KB Output is partially correct
12 Partially correct 200 ms 38508 KB Output is partially correct
13 Correct 136 ms 35304 KB Output is correct
14 Correct 128 ms 32488 KB Output is correct
15 Correct 134 ms 35260 KB Output is correct
16 Correct 136 ms 34088 KB Output is correct
17 Correct 125 ms 28132 KB Output is correct
18 Correct 125 ms 26300 KB Output is correct
19 Correct 174 ms 37964 KB Output is correct
20 Correct 191 ms 37180 KB Output is correct
21 Correct 190 ms 38060 KB Output is correct
22 Partially correct 169 ms 38480 KB Output is partially correct
23 Partially correct 180 ms 38512 KB Output is partially correct
24 Correct 188 ms 37296 KB Output is correct
25 Partially correct 201 ms 39044 KB Output is partially correct
26 Correct 189 ms 37844 KB Output is correct
27 Correct 111 ms 23284 KB Output is correct
28 Partially correct 119 ms 28972 KB Output is partially correct
29 Partially correct 121 ms 29444 KB Output is partially correct
30 Partially correct 132 ms 29496 KB Output is partially correct
31 Correct 129 ms 28656 KB Output is correct
32 Correct 124 ms 28504 KB Output is correct
33 Correct 121 ms 28596 KB Output is correct
34 Correct 117 ms 22972 KB Output is correct
35 Partially correct 122 ms 29240 KB Output is partially correct
36 Correct 127 ms 23272 KB Output is correct
37 Partially correct 116 ms 29212 KB Output is partially correct
38 Partially correct 113 ms 30032 KB Output is partially correct
39 Correct 217 ms 37300 KB Output is correct
40 Correct 214 ms 36336 KB Output is correct
41 Correct 156 ms 29928 KB Output is correct
42 Correct 217 ms 37844 KB Output is correct