oj.uz

Submission #78825

# Submission time Handle Problem Language Result Execution time Memory
78825 2018-10-09T05:40:32 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
51 / 100
 359 ms 8912 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 = 1, hi = N - 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 - 1;
    }
    s = U[hi];
    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 2528 KB Output is correct
2 Correct 4 ms 2344 KB Output is correct
3 Correct 4 ms 2428 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2448 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2444 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 2524 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2492 KB Output is correct
2 Correct 28 ms 2984 KB Output is correct
3 Correct 287 ms 7828 KB Output is correct
4 Correct 238 ms 7960 KB Output is correct
5 Correct 280 ms 7828 KB Output is correct
6 Correct 220 ms 7828 KB Output is correct
7 Correct 263 ms 7924 KB Output is correct
8 Correct 258 ms 7848 KB Output is correct
9 Correct 256 ms 7836 KB Output is correct
10 Correct 197 ms 7828 KB Output is correct
11 Correct 262 ms 7848 KB Output is correct
12 Correct 228 ms 7736 KB Output is correct
13 Correct 252 ms 7736 KB Output is correct
14 Correct 243 ms 7744 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2952 KB Output is correct
2 Correct 23 ms 3612 KB Output is correct
3 Correct 44 ms 4200 KB Output is correct
4 Correct 136 ms 7804 KB Output is correct
5 Correct 182 ms 7840 KB Output is correct
6 Correct 134 ms 7728 KB Output is correct
7 Correct 175 ms 7736 KB Output is correct
8 Correct 140 ms 7852 KB Output is correct
9 Correct 130 ms 7732 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2572 KB Output is correct
2 Correct 38 ms 2964 KB Output is correct
3 Correct 193 ms 6732 KB Output is correct
4 Correct 213 ms 7916 KB Output is correct
5 Correct 254 ms 7892 KB Output is correct
6 Correct 264 ms 7852 KB Output is correct
7 Correct 218 ms 7836 KB Output is correct
8 Correct 239 ms 7836 KB Output is correct
9 Correct 208 ms 7824 KB Output is correct
10 Correct 268 ms 7848 KB Output is correct
11 Correct 245 ms 7744 KB Output is correct
12 Correct 241 ms 7836 KB Output is correct
13 Correct 272 ms 7832 KB Output is correct
14 Correct 262 ms 7752 KB Output is correct
15 Correct 286 ms 7876 KB Output is correct
16 Correct 213 ms 7840 KB Output is correct
17 Correct 259 ms 7740 KB Output is correct
18 Correct 318 ms 7744 KB Output is correct
19 Correct 279 ms 7856 KB Output is correct
20 Correct 238 ms 7736 KB Output is correct
21 Correct 204 ms 8096 KB Output is correct
22 Correct 182 ms 8076 KB Output is correct
23 Correct 245 ms 8208 KB Output is correct
24 Correct 230 ms 8160 KB Output is correct
25 Correct 236 ms 7812 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2984 KB Output is correct
2 Correct 33 ms 3004 KB Output is correct
3 Correct 292 ms 8084 KB Output is correct
4 Correct 272 ms 8292 KB Output is correct
5 Incorrect 359 ms 8912 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3036 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -