oj.uz

Submission #78826

# Submission time Handle Problem Language Result Execution time Memory
78826 2018-10-09T05:41:55 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
51 / 100
 345 ms 8808 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 = 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;
    }
    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 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 2444 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 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 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 2424 KB Output is correct
2 Correct 26 ms 2960 KB Output is correct
3 Correct 255 ms 7888 KB Output is correct
4 Correct 243 ms 7848 KB Output is correct
5 Correct 259 ms 7832 KB Output is correct
6 Correct 222 ms 7876 KB Output is correct
7 Correct 265 ms 7888 KB Output is correct
8 Correct 262 ms 7936 KB Output is correct
9 Correct 267 ms 7840 KB Output is correct
10 Correct 210 ms 7836 KB Output is correct
11 Correct 270 ms 7740 KB Output is correct
12 Correct 258 ms 7740 KB Output is correct
13 Correct 248 ms 7728 KB Output is correct
14 Correct 249 ms 7724 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2956 KB Output is correct
2 Correct 42 ms 3576 KB Output is correct
3 Correct 60 ms 4208 KB Output is correct
4 Correct 204 ms 7736 KB Output is correct
5 Correct 161 ms 7744 KB Output is correct
6 Correct 142 ms 7732 KB Output is correct
7 Correct 177 ms 7736 KB Output is correct
8 Correct 173 ms 7728 KB Output is correct
9 Correct 181 ms 7728 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2492 KB Output is correct
2 Correct 21 ms 3024 KB Output is correct
3 Correct 188 ms 6656 KB Output is correct
4 Correct 257 ms 7984 KB Output is correct
5 Correct 243 ms 7852 KB Output is correct
6 Correct 246 ms 7892 KB Output is correct
7 Correct 234 ms 7948 KB Output is correct
8 Correct 262 ms 7892 KB Output is correct
9 Correct 241 ms 7832 KB Output is correct
10 Correct 252 ms 7916 KB Output is correct
11 Correct 267 ms 7860 KB Output is correct
12 Correct 230 ms 7744 KB Output is correct
13 Correct 272 ms 7724 KB Output is correct
14 Correct 275 ms 7744 KB Output is correct
15 Correct 282 ms 7900 KB Output is correct
16 Correct 239 ms 7932 KB Output is correct
17 Correct 251 ms 7752 KB Output is correct
18 Correct 267 ms 7728 KB Output is correct
19 Correct 276 ms 7832 KB Output is correct
20 Correct 279 ms 7812 KB Output is correct
21 Correct 213 ms 8100 KB Output is correct
22 Correct 206 ms 8096 KB Output is correct
23 Correct 209 ms 8092 KB Output is correct
24 Correct 184 ms 8056 KB Output is correct
25 Correct 229 ms 7776 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3016 KB Output is correct
2 Correct 33 ms 3064 KB Output is correct
3 Correct 312 ms 8072 KB Output is correct
4 Correct 307 ms 8280 KB Output is correct
5 Incorrect 345 ms 8808 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 28 ms 3028 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -