oj.uz

Submission #78834

# Submission time Handle Problem Language Result Execution time Memory
78834 2018-10-09T05:58:10 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
6 / 100
 292 ms 14072 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 - 1;
    }
    assert(hi != -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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2452 KB Output is correct
3 Correct 4 ms 2444 KB Output is correct
4 Correct 4 ms 2428 KB Output is correct
5 Correct 4 ms 2344 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 2448 KB Output is correct
9 Correct 4 ms 2428 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2468 KB Output is correct
12 Runtime error 7 ms 4692 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 27 ms 3068 KB Output is correct
3 Correct 260 ms 7840 KB Output is correct
4 Correct 230 ms 7884 KB Output is correct
5 Correct 261 ms 7848 KB Output is correct
6 Correct 228 ms 7832 KB Output is correct
7 Correct 221 ms 7848 KB Output is correct
8 Correct 247 ms 7940 KB Output is correct
9 Correct 292 ms 7868 KB Output is correct
10 Correct 238 ms 7928 KB Output is correct
11 Correct 266 ms 7732 KB Output is correct
12 Correct 265 ms 7752 KB Output is correct
13 Correct 260 ms 7744 KB Output is correct
14 Runtime error 154 ms 14068 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2936 KB Output is correct
2 Correct 42 ms 3740 KB Output is correct
3 Correct 62 ms 4308 KB Output is correct
4 Correct 161 ms 7748 KB Output is correct
5 Correct 180 ms 7728 KB Output is correct
6 Correct 158 ms 7720 KB Output is correct
7 Correct 201 ms 7732 KB Output is correct
8 Correct 136 ms 7724 KB Output is correct
9 Correct 206 ms 7752 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 28 ms 2936 KB Output is correct
3 Correct 226 ms 6672 KB Output is correct
4 Correct 271 ms 7848 KB Output is correct
5 Correct 275 ms 7900 KB Output is correct
6 Correct 250 ms 7884 KB Output is correct
7 Correct 221 ms 7824 KB Output is correct
8 Correct 276 ms 7916 KB Output is correct
9 Correct 245 ms 7860 KB Output is correct
10 Correct 267 ms 7848 KB Output is correct
11 Correct 247 ms 7796 KB Output is correct
12 Correct 234 ms 7816 KB Output is correct
13 Correct 276 ms 7744 KB Output is correct
14 Correct 277 ms 7748 KB Output is correct
15 Correct 271 ms 7840 KB Output is correct
16 Correct 223 ms 7904 KB Output is correct
17 Correct 246 ms 7760 KB Output is correct
18 Runtime error 194 ms 14072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3032 KB Output is correct
2 Correct 56 ms 3000 KB Output is correct
3 Incorrect 285 ms 8064 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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