oj.uz

Submission #78831

# Submission time Handle Problem Language Result Execution time Memory
78831 2018-10-09T05:49:35 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
51 / 100
 372 ms 8920 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;

int q[MAXN], to[MAXN];
vector<int> adj[MAXN];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = sz(U), front, back, s = 0, lo = 0, hi = M - 1, mid, v;
    FOR(i, M) {
        adj[U[i]].pb(i);
        adj[V[i]].pb(i);
    }
    vector<int> Q(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;
    }
    s = U[lo];
    vector<int> ans;
    FOR(_, 2) {
        front = 0, back = 0, lo = 1, hi = N - 1;
        fill(to, to + N, -1);
        to[q[back++] = s] = -INT_INF;
        while (front < back) FORE(e, adj[v = q[front++]]) if (to[v ^ U[e] ^ V[e]] == -1) to[q[back++] = v ^ U[e] ^ V[e]] = e;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            fill(all(Q), 0);
            For(i, mid, N) Q[to[q[i]]] = 1;
            if (ask(Q) == DA) hi = mid - 1;
            else lo = mid + 1;
        }
        ans.pb(s = q[hi]);
    }
    answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2340 KB Output is correct
2 Correct 4 ms 2440 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2428 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2344 KB Output is correct
9 Correct 4 ms 2448 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2444 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 2496 KB Output is correct
2 Correct 21 ms 3064 KB Output is correct
3 Correct 258 ms 7888 KB Output is correct
4 Correct 222 ms 7836 KB Output is correct
5 Correct 256 ms 7944 KB Output is correct
6 Correct 205 ms 7840 KB Output is correct
7 Correct 259 ms 7852 KB Output is correct
8 Correct 258 ms 7868 KB Output is correct
9 Correct 242 ms 7908 KB Output is correct
10 Correct 241 ms 7916 KB Output is correct
11 Correct 287 ms 7744 KB Output is correct
12 Correct 273 ms 7748 KB Output is correct
13 Correct 285 ms 7780 KB Output is correct
14 Correct 264 ms 7748 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2984 KB Output is correct
2 Correct 41 ms 3624 KB Output is correct
3 Correct 58 ms 4208 KB Output is correct
4 Correct 188 ms 7780 KB Output is correct
5 Correct 209 ms 7736 KB Output is correct
6 Correct 188 ms 7840 KB Output is correct
7 Correct 186 ms 7760 KB Output is correct
8 Correct 182 ms 7724 KB Output is correct
9 Correct 183 ms 7864 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2488 KB Output is correct
2 Correct 22 ms 3108 KB Output is correct
3 Correct 202 ms 6712 KB Output is correct
4 Correct 267 ms 7860 KB Output is correct
5 Correct 263 ms 7848 KB Output is correct
6 Correct 259 ms 7892 KB Output is correct
7 Correct 263 ms 7876 KB Output is correct
8 Correct 277 ms 7840 KB Output is correct
9 Correct 257 ms 7844 KB Output is correct
10 Correct 256 ms 7832 KB Output is correct
11 Correct 268 ms 7768 KB Output is correct
12 Correct 242 ms 7744 KB Output is correct
13 Correct 256 ms 7748 KB Output is correct
14 Correct 299 ms 7736 KB Output is correct
15 Correct 260 ms 7988 KB Output is correct
16 Correct 260 ms 7844 KB Output is correct
17 Correct 232 ms 7784 KB Output is correct
18 Correct 286 ms 7732 KB Output is correct
19 Correct 253 ms 7844 KB Output is correct
20 Correct 269 ms 7736 KB Output is correct
21 Correct 207 ms 8192 KB Output is correct
22 Correct 204 ms 8208 KB Output is correct
23 Correct 206 ms 8084 KB Output is correct
24 Correct 206 ms 8056 KB Output is correct
25 Correct 211 ms 7780 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2988 KB Output is correct
2 Correct 29 ms 3044 KB Output is correct
3 Correct 276 ms 8072 KB Output is correct
4 Correct 276 ms 8416 KB Output is correct
5 Correct 372 ms 8920 KB Output is correct
6 Incorrect 370 ms 8800 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2984 KB Output is correct
2 Correct 29 ms 3064 KB Output is correct
3 Partially correct 286 ms 8092 KB Output is partially correct
4 Correct 307 ms 8188 KB Output is correct
5 Correct 319 ms 8296 KB Output is correct
6 Incorrect 331 ms 8796 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -