oj.uz

Submission #78821

# Submission time Handle Problem Language Result Execution time Memory
78821 2018-10-09T05:23:41 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
51 / 100
 343 ms 8828 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);
    FOR(i, M) {
        adj[U[i]].pb(i);
        adj[V[i]].pb(i);
    }
    vector<int> Q(M, 0);
    ll DA = ask(Q);
    int s = 0;
    vector<int> ans;
    FOR(_, 2) {
        int front = 0, back = 0, lo = 1, hi = N - 1, mid, v;
        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 2448 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2440 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 2528 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2532 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 2444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2576 KB Output is correct
2 Correct 26 ms 2936 KB Output is correct
3 Correct 254 ms 7840 KB Output is correct
4 Correct 238 ms 7864 KB Output is correct
5 Correct 254 ms 7852 KB Output is correct
6 Correct 213 ms 7836 KB Output is correct
7 Correct 266 ms 7940 KB Output is correct
8 Correct 288 ms 7884 KB Output is correct
9 Correct 205 ms 7828 KB Output is correct
10 Correct 241 ms 7840 KB Output is correct
11 Correct 265 ms 7732 KB Output is correct
12 Correct 269 ms 7804 KB Output is correct
13 Correct 302 ms 7828 KB Output is correct
14 Correct 261 ms 7732 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3032 KB Output is correct
2 Correct 41 ms 3576 KB Output is correct
3 Correct 58 ms 4204 KB Output is correct
4 Correct 175 ms 7732 KB Output is correct
5 Correct 166 ms 7732 KB Output is correct
6 Correct 154 ms 7852 KB Output is correct
7 Correct 110 ms 7728 KB Output is correct
8 Correct 144 ms 7728 KB Output is correct
9 Correct 116 ms 7728 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2596 KB Output is correct
2 Correct 25 ms 3024 KB Output is correct
3 Correct 179 ms 6736 KB Output is correct
4 Correct 230 ms 7852 KB Output is correct
5 Correct 226 ms 7828 KB Output is correct
6 Correct 226 ms 7824 KB Output is correct
7 Correct 228 ms 7824 KB Output is correct
8 Correct 253 ms 7896 KB Output is correct
9 Correct 228 ms 7840 KB Output is correct
10 Correct 239 ms 7840 KB Output is correct
11 Correct 275 ms 7748 KB Output is correct
12 Correct 200 ms 7736 KB Output is correct
13 Correct 211 ms 7852 KB Output is correct
14 Correct 225 ms 7744 KB Output is correct
15 Correct 218 ms 7832 KB Output is correct
16 Correct 243 ms 7844 KB Output is correct
17 Correct 247 ms 7736 KB Output is correct
18 Correct 267 ms 7740 KB Output is correct
19 Correct 288 ms 7908 KB Output is correct
20 Correct 269 ms 7720 KB Output is correct
21 Correct 209 ms 8100 KB Output is correct
22 Correct 188 ms 8192 KB Output is correct
23 Correct 198 ms 8200 KB Output is correct
24 Correct 196 ms 8148 KB Output is correct
25 Correct 230 ms 7776 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3072 KB Output is correct
2 Correct 28 ms 3036 KB Output is correct
3 Correct 286 ms 8076 KB Output is correct
4 Correct 295 ms 8308 KB Output is correct
5 Incorrect 343 ms 8828 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 35 ms 3064 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -