oj.uz

Submission #535427

# Submission time Handle Problem Language Result Execution time Memory
535427 2022-03-10T09:19:19 Z mario05092929 Highway Tolls (IOI18_highway) C++14
100 / 100
 233 ms 11312 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 1e9;
int n,m,p[100005],idx[100005];
vec v[100005];
vec w;
ll a,b,dist;
int d[2][100005],wh,c[100005];
vec num[2];
vector <pi> ed;

bool cmp(int x,int y) {
    return d[wh][x] < d[wh][y];
}

int Find_edge() {
    int l = 0,r = m-1;
    while(l < r) {
        int mid = (l + r) >> 1;
        w.clear(); w.resize(m,0);
        for(int i = 0;i <= mid;i++) w[i] = 1;
        if(ask(w) > dist) r = mid;
        else l = mid+1;
    }
    return l;
}

void BFS(int st,int no,int co) {
    queue <int> q; q.push(st);
    for(int i = 1;i <= n;i++) d[co][i] = INF;
    d[co][st] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i : v[x]) {
            if(d[co][i] == INF) {
                d[co][i] = d[co][x]+1;
                q.push(i);
            }
        }
    }
}

int Find(int co) {
    int l = 0,r = num[co].size()-1;
    int g = 1;
    memset(c,0,sizeof(c));
    while(l < r) {
        int mid = (l + r) >> 1;
        w.clear(); w.resize(m,0);
        for(int i = mid+1;i <= r;i++) c[num[co][i]] = g;
        for(int i = 0;i < m;i++) if(c[ed[i].x] == g||c[ed[i].y] == g) w[i] = 1;
        if(ask(w) > dist) l = mid+1;
        else r = mid;
        g++;
    }
    return num[co][l];
}

void find_pair(int N,vec U,vec V,int A,int B) {
    a = A, b = B;
    n = N, m = U.size();
    for(int i = 0;i < m;i++) {
        U[i]++, V[i]++;
        ed.push_back({U[i],V[i]});
        v[U[i]].push_back(V[i]);
        v[V[i]].push_back(U[i]);
    }
    dist = ask(vector<int>(m,0));
    int edge = Find_edge(),l = U[edge],r = V[edge];
    BFS(l,r,0), BFS(r,l,1);
    for(int i = 1;i <= n;i++) {
        if(d[0][i] < d[1][i]) num[0].push_back(i);
        else num[1].push_back(i);
    }
    sort(num[0].begin(),num[0].end(),cmp); wh = 1;
    sort(num[1].begin(),num[1].end(),cmp);
    answer(Find(0)-1,Find(1)-1);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3024 KB Output is correct
2 Correct 18 ms 3760 KB Output is correct
3 Correct 113 ms 10040 KB Output is correct
4 Correct 134 ms 10048 KB Output is correct
5 Correct 139 ms 10052 KB Output is correct
6 Correct 128 ms 10064 KB Output is correct
7 Correct 153 ms 10040 KB Output is correct
8 Correct 138 ms 10032 KB Output is correct
9 Correct 138 ms 10028 KB Output is correct
10 Correct 166 ms 10036 KB Output is correct
11 Correct 155 ms 9752 KB Output is correct
12 Correct 179 ms 9844 KB Output is correct
13 Correct 161 ms 9916 KB Output is correct
14 Correct 143 ms 9884 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3784 KB Output is correct
2 Correct 27 ms 4484 KB Output is correct
3 Correct 69 ms 5248 KB Output is correct
4 Correct 105 ms 9620 KB Output is correct
5 Correct 95 ms 9664 KB Output is correct
6 Correct 126 ms 9924 KB Output is correct
7 Correct 95 ms 9900 KB Output is correct
8 Correct 95 ms 9656 KB Output is correct
9 Correct 101 ms 9816 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3024 KB Output is correct
2 Correct 14 ms 3816 KB Output is correct
3 Correct 95 ms 8632 KB Output is correct
4 Correct 122 ms 10036 KB Output is correct
5 Correct 120 ms 10052 KB Output is correct
6 Correct 111 ms 10036 KB Output is correct
7 Correct 144 ms 10044 KB Output is correct
8 Correct 120 ms 10024 KB Output is correct
9 Correct 132 ms 10008 KB Output is correct
10 Correct 174 ms 10040 KB Output is correct
11 Correct 174 ms 9908 KB Output is correct
12 Correct 147 ms 9876 KB Output is correct
13 Correct 135 ms 9840 KB Output is correct
14 Correct 146 ms 9620 KB Output is correct
15 Correct 145 ms 10032 KB Output is correct
16 Correct 107 ms 10040 KB Output is correct
17 Correct 154 ms 9880 KB Output is correct
18 Correct 171 ms 9896 KB Output is correct
19 Correct 149 ms 10076 KB Output is correct
20 Correct 183 ms 9880 KB Output is correct
21 Correct 131 ms 10276 KB Output is correct
22 Correct 98 ms 10284 KB Output is correct
23 Correct 111 ms 10284 KB Output is correct
24 Correct 122 ms 10096 KB Output is correct
25 Correct 137 ms 9948 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3744 KB Output is correct
2 Correct 21 ms 3784 KB Output is correct
3 Correct 160 ms 10352 KB Output is correct
4 Correct 161 ms 10468 KB Output is correct
5 Correct 233 ms 11312 KB Output is correct
6 Correct 195 ms 11272 KB Output is correct
7 Correct 186 ms 11272 KB Output is correct
8 Correct 188 ms 11032 KB Output is correct
9 Correct 146 ms 8744 KB Output is correct
10 Correct 140 ms 9140 KB Output is correct
11 Correct 155 ms 9384 KB Output is correct
12 Correct 160 ms 10484 KB Output is correct
13 Correct 182 ms 10724 KB Output is correct
14 Correct 180 ms 10840 KB Output is correct
15 Correct 169 ms 10860 KB Output is correct
16 Correct 177 ms 9644 KB Output is correct
17 Correct 144 ms 10364 KB Output is correct
18 Correct 104 ms 10420 KB Output is correct
19 Correct 106 ms 10376 KB Output is correct
20 Correct 123 ms 10484 KB Output is correct
21 Correct 169 ms 11192 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3816 KB Output is correct
2 Correct 17 ms 3896 KB Output is correct
3 Correct 144 ms 10012 KB Output is correct
4 Correct 170 ms 10440 KB Output is correct
5 Correct 163 ms 10600 KB Output is correct
6 Correct 169 ms 11204 KB Output is correct
7 Correct 154 ms 10388 KB Output is correct
8 Correct 130 ms 10488 KB Output is correct
9 Correct 148 ms 10452 KB Output is correct
10 Correct 179 ms 11272 KB Output is correct
11 Correct 194 ms 11228 KB Output is correct
12 Correct 178 ms 11184 KB Output is correct
13 Correct 133 ms 9372 KB Output is correct
14 Correct 119 ms 9080 KB Output is correct
15 Correct 129 ms 9388 KB Output is correct
16 Correct 135 ms 9132 KB Output is correct
17 Correct 132 ms 9372 KB Output is correct
18 Correct 121 ms 9184 KB Output is correct
19 Correct 145 ms 10488 KB Output is correct
20 Correct 183 ms 10600 KB Output is correct
21 Correct 191 ms 10852 KB Output is correct
22 Correct 193 ms 10908 KB Output is correct
23 Correct 171 ms 11048 KB Output is correct
24 Correct 172 ms 10924 KB Output is correct
25 Correct 171 ms 11052 KB Output is correct
26 Correct 190 ms 11260 KB Output is correct
27 Correct 111 ms 10420 KB Output is correct
28 Correct 107 ms 10356 KB Output is correct
29 Correct 109 ms 10528 KB Output is correct
30 Correct 95 ms 10436 KB Output is correct
31 Correct 110 ms 10400 KB Output is correct
32 Correct 114 ms 10320 KB Output is correct
33 Correct 111 ms 10524 KB Output is correct
34 Correct 107 ms 10388 KB Output is correct
35 Correct 106 ms 10376 KB Output is correct
36 Correct 116 ms 10308 KB Output is correct
37 Correct 119 ms 10496 KB Output is correct
38 Correct 111 ms 10500 KB Output is correct
39 Correct 165 ms 11156 KB Output is correct
40 Correct 177 ms 11176 KB Output is correct
41 Correct 167 ms 11240 KB Output is correct
42 Correct 182 ms 10948 KB Output is correct