oj.uz

Submission #131766

# Submission time Handle Problem Language Result Execution time Memory
131766 2019-07-17T15:25:18 Z WannnabeIOI Highway Tolls (IOI18_highway) C++14
100 / 100
 395 ms 9492 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXN = 90005, MAXM = 130005;

int to[MAXN], ans[2];
bool tr[MAXM];
vector<int> adj[MAXN], verts[2];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = sz(U), lo = 0, hi = M - 1, mid;
    FOR(i, M) {
        adj[U[i]].pb(i);
        adj[V[i]].pb(i);
    }
    vector<int> Q(M, 0);
    fill(tr, tr + M, 0);
    ll DA = ask(Q);
    while (lo < hi) {
        mid = lo + (hi - lo) / 2;
        FOR(i, M) Q[i] = i <= mid;
        if (ask(Q) == DA) lo = mid + 1;
        else hi = mid;
    }
    fill(to, to + N, -1);
    queue<pii> q;
    q.emplace(U[lo], 0);
    q.emplace(V[lo], 1);
    tr[lo] = 1;
    to[U[lo]] = to[V[lo]] = -INT_INF;
    while (!q.empty()) {
        pii v = q.front();
        q.pop();
        verts[v.s].pb(v.f);
        FORE(e, adj[v.f]) {
            int w = v.f ^ U[e] ^ V[e];
            if (to[w] != -1) continue;
            q.emplace(w, v.s);
            tr[to[w] = e] = 1;
        }
    }
    FOR(i, 2) {
        lo = 1, hi = sz(verts[i]) - 1;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            FOR(j, M) Q[j] = !tr[j];
            For(j, mid, sz(verts[i])) Q[to[verts[i][j]]] = 1;
            if (ask(Q) == DA) hi = mid - 1;
            else lo = mid + 1;
        }
        ans[i] = verts[i][hi];
    }
    answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2448 KB Output is correct
2 Correct 4 ms 2428 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2440 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2444 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2440 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2556 KB Output is correct
2 Correct 25 ms 3212 KB Output is correct
3 Correct 207 ms 8116 KB Output is correct
4 Correct 203 ms 8240 KB Output is correct
5 Correct 222 ms 8236 KB Output is correct
6 Correct 207 ms 8120 KB Output is correct
7 Correct 215 ms 8248 KB Output is correct
8 Correct 233 ms 8188 KB Output is correct
9 Correct 220 ms 8196 KB Output is correct
10 Correct 218 ms 8112 KB Output is correct
11 Correct 246 ms 7992 KB Output is correct
12 Correct 248 ms 8136 KB Output is correct
13 Correct 231 ms 8148 KB Output is correct
14 Correct 243 ms 8216 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3064 KB Output is correct
2 Correct 62 ms 3700 KB Output is correct
3 Correct 62 ms 4336 KB Output is correct
4 Correct 161 ms 8064 KB Output is correct
5 Correct 171 ms 8040 KB Output is correct
6 Correct 160 ms 8144 KB Output is correct
7 Correct 174 ms 8140 KB Output is correct
8 Correct 183 ms 8012 KB Output is correct
9 Correct 179 ms 8112 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 26 ms 2984 KB Output is correct
3 Correct 177 ms 7088 KB Output is correct
4 Correct 232 ms 8236 KB Output is correct
5 Correct 212 ms 8108 KB Output is correct
6 Correct 239 ms 8128 KB Output is correct
7 Correct 227 ms 8128 KB Output is correct
8 Correct 227 ms 8116 KB Output is correct
9 Correct 219 ms 8396 KB Output is correct
10 Correct 229 ms 8264 KB Output is correct
11 Correct 233 ms 8108 KB Output is correct
12 Correct 221 ms 8280 KB Output is correct
13 Correct 277 ms 8184 KB Output is correct
14 Correct 226 ms 8080 KB Output is correct
15 Correct 199 ms 8224 KB Output is correct
16 Correct 222 ms 8224 KB Output is correct
17 Correct 225 ms 8200 KB Output is correct
18 Correct 219 ms 8160 KB Output is correct
19 Correct 222 ms 8208 KB Output is correct
20 Correct 226 ms 8020 KB Output is correct
21 Correct 181 ms 9272 KB Output is correct
22 Correct 172 ms 9208 KB Output is correct
23 Correct 220 ms 8680 KB Output is correct
24 Correct 209 ms 8656 KB Output is correct
25 Correct 211 ms 8184 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3108 KB Output is correct
2 Correct 29 ms 3200 KB Output is correct
3 Correct 238 ms 8508 KB Output is correct
4 Correct 262 ms 8848 KB Output is correct
5 Correct 324 ms 9460 KB Output is correct
6 Correct 318 ms 9400 KB Output is correct
7 Correct 340 ms 9356 KB Output is correct
8 Correct 328 ms 9324 KB Output is correct
9 Correct 259 ms 7336 KB Output is correct
10 Correct 234 ms 7736 KB Output is correct
11 Correct 254 ms 7904 KB Output is correct
12 Correct 303 ms 8944 KB Output is correct
13 Correct 316 ms 9140 KB Output is correct
14 Correct 307 ms 9180 KB Output is correct
15 Correct 323 ms 9104 KB Output is correct
16 Correct 263 ms 8068 KB Output is correct
17 Correct 200 ms 9224 KB Output is correct
18 Correct 220 ms 9260 KB Output is correct
19 Correct 171 ms 9268 KB Output is correct
20 Correct 231 ms 9328 KB Output is correct
21 Correct 307 ms 9188 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3116 KB Output is correct
2 Correct 30 ms 3148 KB Output is correct
3 Correct 289 ms 8508 KB Output is correct
4 Correct 252 ms 8640 KB Output is correct
5 Correct 291 ms 8744 KB Output is correct
6 Correct 318 ms 9384 KB Output is correct
7 Correct 225 ms 8500 KB Output is correct
8 Correct 264 ms 8592 KB Output is correct
9 Correct 281 ms 8808 KB Output is correct
10 Correct 325 ms 9316 KB Output is correct
11 Correct 331 ms 9260 KB Output is correct
12 Correct 330 ms 9312 KB Output is correct
13 Correct 256 ms 7964 KB Output is correct
14 Correct 233 ms 7680 KB Output is correct
15 Correct 250 ms 7984 KB Output is correct
16 Correct 244 ms 7696 KB Output is correct
17 Correct 258 ms 7864 KB Output is correct
18 Correct 248 ms 7660 KB Output is correct
19 Correct 294 ms 8748 KB Output is correct
20 Correct 319 ms 8976 KB Output is correct
21 Correct 315 ms 9144 KB Output is correct
22 Correct 348 ms 9188 KB Output is correct
23 Correct 317 ms 9208 KB Output is correct
24 Correct 365 ms 9136 KB Output is correct
25 Correct 332 ms 9232 KB Output is correct
26 Correct 317 ms 9232 KB Output is correct
27 Correct 208 ms 9284 KB Output is correct
28 Correct 219 ms 9204 KB Output is correct
29 Correct 220 ms 9440 KB Output is correct
30 Correct 199 ms 8916 KB Output is correct
31 Correct 198 ms 9252 KB Output is correct
32 Correct 199 ms 9184 KB Output is correct
33 Correct 217 ms 9376 KB Output is correct
34 Correct 222 ms 9240 KB Output is correct
35 Correct 205 ms 9140 KB Output is correct
36 Correct 209 ms 9176 KB Output is correct
37 Correct 296 ms 9492 KB Output is correct
38 Correct 198 ms 9180 KB Output is correct
39 Correct 305 ms 9228 KB Output is correct
40 Correct 309 ms 9176 KB Output is correct
41 Correct 395 ms 9060 KB Output is correct
42 Correct 323 ms 9180 KB Output is correct