oj.uz

Submission #78948

# Submission time Handle Problem Language Result Execution time Memory
78948 2018-10-09T17:16:44 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
100 / 100
 346 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 2344 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2528 KB Output is correct
5 Correct 4 ms 2452 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2440 KB Output is correct
8 Correct 4 ms 2424 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 2424 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 5 ms 2576 KB Output is correct
2 Correct 25 ms 3112 KB Output is correct
3 Correct 221 ms 8200 KB Output is correct
4 Correct 242 ms 8240 KB Output is correct
5 Correct 213 ms 8240 KB Output is correct
6 Correct 198 ms 8116 KB Output is correct
7 Correct 225 ms 8160 KB Output is correct
8 Correct 223 ms 8252 KB Output is correct
9 Correct 231 ms 8108 KB Output is correct
10 Correct 200 ms 8240 KB Output is correct
11 Correct 233 ms 8092 KB Output is correct
12 Correct 266 ms 8148 KB Output is correct
13 Correct 215 ms 8020 KB Output is correct
14 Correct 238 ms 8208 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3112 KB Output is correct
2 Correct 51 ms 3700 KB Output is correct
3 Correct 44 ms 4492 KB Output is correct
4 Correct 186 ms 8024 KB Output is correct
5 Correct 168 ms 8072 KB Output is correct
6 Correct 152 ms 8216 KB Output is correct
7 Correct 174 ms 8220 KB Output is correct
8 Correct 179 ms 8016 KB Output is correct
9 Correct 174 ms 8120 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2552 KB Output is correct
2 Correct 27 ms 3064 KB Output is correct
3 Correct 176 ms 7072 KB Output is correct
4 Correct 205 ms 8248 KB Output is correct
5 Correct 222 ms 8148 KB Output is correct
6 Correct 234 ms 8116 KB Output is correct
7 Correct 226 ms 8128 KB Output is correct
8 Correct 227 ms 8112 KB Output is correct
9 Correct 224 ms 8376 KB Output is correct
10 Correct 224 ms 8248 KB Output is correct
11 Correct 225 ms 8080 KB Output is correct
12 Correct 218 ms 8272 KB Output is correct
13 Correct 238 ms 8188 KB Output is correct
14 Correct 253 ms 8000 KB Output is correct
15 Correct 246 ms 8348 KB Output is correct
16 Correct 215 ms 8228 KB Output is correct
17 Correct 236 ms 8212 KB Output is correct
18 Correct 243 ms 8164 KB Output is correct
19 Correct 220 ms 8104 KB Output is correct
20 Correct 235 ms 8012 KB Output is correct
21 Correct 176 ms 9332 KB Output is correct
22 Correct 189 ms 9276 KB Output is correct
23 Correct 210 ms 8700 KB Output is correct
24 Correct 223 ms 8668 KB Output is correct
25 Correct 201 ms 8180 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3112 KB Output is correct
2 Correct 48 ms 3144 KB Output is correct
3 Correct 227 ms 8468 KB Output is correct
4 Correct 271 ms 8824 KB Output is correct
5 Correct 328 ms 9492 KB Output is correct
6 Correct 316 ms 9328 KB Output is correct
7 Correct 308 ms 9352 KB Output is correct
8 Correct 309 ms 9300 KB Output is correct
9 Correct 233 ms 7336 KB Output is correct
10 Correct 252 ms 7812 KB Output is correct
11 Correct 235 ms 7856 KB Output is correct
12 Correct 299 ms 8920 KB Output is correct
13 Correct 336 ms 9144 KB Output is correct
14 Correct 330 ms 9132 KB Output is correct
15 Correct 346 ms 9112 KB Output is correct
16 Correct 274 ms 8212 KB Output is correct
17 Correct 202 ms 9216 KB Output is correct
18 Correct 219 ms 9272 KB Output is correct
19 Correct 192 ms 9276 KB Output is correct
20 Correct 218 ms 9312 KB Output is correct
21 Correct 314 ms 9268 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3112 KB Output is correct
2 Correct 54 ms 3148 KB Output is correct
3 Correct 281 ms 8612 KB Output is correct
4 Correct 279 ms 8676 KB Output is correct
5 Correct 293 ms 8800 KB Output is correct
6 Correct 312 ms 9284 KB Output is correct
7 Correct 226 ms 8500 KB Output is correct
8 Correct 273 ms 8588 KB Output is correct
9 Correct 275 ms 8772 KB Output is correct
10 Correct 329 ms 9364 KB Output is correct
11 Correct 334 ms 9248 KB Output is correct
12 Correct 309 ms 9308 KB Output is correct
13 Correct 242 ms 7984 KB Output is correct
14 Correct 240 ms 7776 KB Output is correct
15 Correct 244 ms 8048 KB Output is correct
16 Correct 232 ms 7764 KB Output is correct
17 Correct 254 ms 7888 KB Output is correct
18 Correct 244 ms 7672 KB Output is correct
19 Correct 309 ms 8756 KB Output is correct
20 Correct 307 ms 8968 KB Output is correct
21 Correct 346 ms 9124 KB Output is correct
22 Correct 327 ms 9196 KB Output is correct
23 Correct 323 ms 9260 KB Output is correct
24 Correct 332 ms 9136 KB Output is correct
25 Correct 346 ms 9208 KB Output is correct
26 Correct 322 ms 9228 KB Output is correct
27 Correct 186 ms 9260 KB Output is correct
28 Correct 229 ms 9200 KB Output is correct
29 Correct 223 ms 9440 KB Output is correct
30 Correct 189 ms 8904 KB Output is correct
31 Correct 217 ms 9260 KB Output is correct
32 Correct 194 ms 9172 KB Output is correct
33 Correct 214 ms 9396 KB Output is correct
34 Correct 220 ms 9276 KB Output is correct
35 Correct 247 ms 9208 KB Output is correct
36 Correct 210 ms 9172 KB Output is correct
37 Correct 222 ms 9476 KB Output is correct
38 Correct 203 ms 9176 KB Output is correct
39 Correct 331 ms 9112 KB Output is correct
40 Correct 319 ms 9168 KB Output is correct
41 Correct 301 ms 9176 KB Output is correct
42 Correct 329 ms 9136 KB Output is correct