oj.uz

Submission #999576

# Submission time Handle Problem Language Result Execution time Memory
999576 2024-06-15T20:27:06 Z amine_aroua Highway Tolls (IOI18_highway) C++17
90 / 100
 219 ms 12380 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 = zeros;
        forr(j , 0 , mid - 1) {
            for(auto i : adj[nds[j].second])asked[i.second] = 1;
        }
        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(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 2392 KB Output is correct
2 Correct 14 ms 3432 KB Output is correct
3 Correct 155 ms 10408 KB Output is correct
4 Correct 128 ms 10152 KB Output is correct
5 Correct 143 ms 10276 KB Output is correct
6 Correct 119 ms 10168 KB Output is correct
7 Correct 153 ms 10152 KB Output is correct
8 Correct 146 ms 10164 KB Output is correct
9 Correct 146 ms 10168 KB Output is correct
10 Correct 135 ms 10272 KB Output is correct
11 Correct 138 ms 9584 KB Output is correct
12 Correct 144 ms 9584 KB Output is correct
13 Correct 141 ms 9584 KB Output is correct
14 Correct 122 ms 9580 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 4140 KB Output is correct
3 Correct 26 ms 4800 KB Output is correct
4 Correct 87 ms 9584 KB Output is correct
5 Correct 87 ms 9584 KB Output is correct
6 Correct 78 ms 9564 KB Output is correct
7 Correct 78 ms 9596 KB Output is correct
8 Correct 84 ms 9828 KB Output is correct
9 Correct 79 ms 9592 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 14 ms 3412 KB Output is correct
3 Correct 117 ms 8720 KB Output is correct
4 Correct 143 ms 10248 KB Output is correct
5 Correct 134 ms 10160 KB Output is correct
6 Correct 147 ms 10176 KB Output is correct
7 Correct 138 ms 10168 KB Output is correct
8 Correct 148 ms 10164 KB Output is correct
9 Correct 135 ms 10328 KB Output is correct
10 Correct 152 ms 10168 KB Output is correct
11 Correct 138 ms 9840 KB Output is correct
12 Correct 123 ms 9592 KB Output is correct
13 Correct 126 ms 9576 KB Output is correct
14 Correct 143 ms 9588 KB Output is correct
15 Correct 150 ms 10184 KB Output is correct
16 Correct 158 ms 10176 KB Output is correct
17 Correct 133 ms 9632 KB Output is correct
18 Correct 142 ms 9640 KB Output is correct
19 Correct 140 ms 10180 KB Output is correct
20 Correct 129 ms 9588 KB Output is correct
21 Correct 96 ms 10584 KB Output is correct
22 Correct 96 ms 10400 KB Output is correct
23 Correct 108 ms 10344 KB Output is correct
24 Correct 99 ms 10328 KB Output is correct
25 Correct 115 ms 9776 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3416 KB Output is correct
2 Correct 16 ms 3512 KB Output is correct
3 Correct 136 ms 10576 KB Output is correct
4 Correct 166 ms 11248 KB Output is correct
5 Correct 186 ms 12128 KB Output is correct
6 Correct 175 ms 12084 KB Output is correct
7 Correct 175 ms 12100 KB Output is correct
8 Correct 173 ms 12092 KB Output is correct
9 Correct 115 ms 9680 KB Output is correct
10 Correct 114 ms 10112 KB Output is correct
11 Correct 111 ms 10676 KB Output is correct
12 Correct 166 ms 11644 KB Output is correct
13 Correct 171 ms 11876 KB Output is correct
14 Correct 176 ms 12092 KB Output is correct
15 Correct 163 ms 12092 KB Output is correct
16 Correct 152 ms 11024 KB Output is correct
17 Correct 93 ms 10460 KB Output is correct
18 Correct 117 ms 10900 KB Output is correct
19 Correct 108 ms 10572 KB Output is correct
20 Correct 104 ms 10660 KB Output is correct
21 Correct 219 ms 12112 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3416 KB Output is correct
2 Correct 13 ms 3528 KB Output is correct
3 Correct 151 ms 10796 KB Output is correct
4 Correct 157 ms 10820 KB Output is correct
5 Correct 144 ms 11284 KB Output is correct
6 Partially correct 167 ms 12064 KB Output is partially correct
7 Partially correct 130 ms 10620 KB Output is partially correct
8 Correct 154 ms 10836 KB Output is correct
9 Partially correct 161 ms 11088 KB Output is partially correct
10 Correct 183 ms 12120 KB Output is correct
11 Partially correct 169 ms 12104 KB Output is partially correct
12 Partially correct 178 ms 12292 KB Output is partially correct
13 Correct 117 ms 10600 KB Output is correct
14 Correct 116 ms 10112 KB Output is correct
15 Correct 123 ms 10604 KB Output is correct
16 Correct 119 ms 10120 KB Output is correct
17 Correct 116 ms 10592 KB Output is correct
18 Correct 112 ms 10192 KB Output is correct
19 Correct 157 ms 11656 KB Output is correct
20 Correct 189 ms 11924 KB Output is correct
21 Correct 179 ms 12116 KB Output is correct
22 Partially correct 158 ms 12228 KB Output is partially correct
23 Partially correct 154 ms 12100 KB Output is partially correct
24 Correct 175 ms 12380 KB Output is correct
25 Partially correct 179 ms 12328 KB Output is partially correct
26 Correct 195 ms 12120 KB Output is correct
27 Partially correct 101 ms 10604 KB Output is partially correct
28 Partially correct 102 ms 10596 KB Output is partially correct
29 Partially correct 124 ms 10736 KB Output is partially correct
30 Partially correct 115 ms 10840 KB Output is partially correct
31 Correct 112 ms 10560 KB Output is correct
32 Correct 104 ms 10480 KB Output is correct
33 Correct 112 ms 10992 KB Output is correct
34 Correct 118 ms 10576 KB Output is correct
35 Partially correct 111 ms 10664 KB Output is partially correct
36 Partially correct 119 ms 10600 KB Output is partially correct
37 Partially correct 100 ms 10672 KB Output is partially correct
38 Partially correct 100 ms 10620 KB Output is partially correct
39 Partially correct 201 ms 12124 KB Output is partially correct
40 Correct 200 ms 12224 KB Output is correct
41 Partially correct 167 ms 12144 KB Output is partially correct
42 Correct 198 ms 12104 KB Output is correct