oj.uz

Submission #78811

# Submission time Handle Problem Language Result Execution time Memory
78811 2018-10-09T04:30:45 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
12 / 100
 315 ms 8556 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;

bool vis[MAXN];
int q[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(V[i]);
        adj[V[i]].pb(U[i]);
    }
    vector<int> Q(M, 0);
    ll DA = ask(Q);
    int s = 0;
    vector<int> ans;
    FOR(_, 2) {
        fill(vis, vis + N, 0);
        int front = 0, back = 0;
        q[back++] = s;
        vis[s] = 1;
        while (front < back) {
            int v = q[front++];
            FORE(w, adj[v]) {
                if (vis[w]) continue;
                vis[w] = 1;
                q[back++] = w;
            }
        }
        int lo = 0, hi = N - 1, mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            FOR(i, mid) vis[q[i]] = 0;
            For(i, mid, N) vis[q[i]] = 1;
            FOR(i, M) Q[i] = vis[U[i]] ^ vis[V[i]];
            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 2520 KB Output is correct
2 Correct 4 ms 2448 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2440 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2428 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 5 ms 2344 KB Output is correct
9 Correct 4 ms 2428 KB Output is correct
10 Correct 4 ms 2436 KB Output is correct
11 Correct 4 ms 2424 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 2400 KB Output is correct
2 Correct 19 ms 2984 KB Output is correct
3 Correct 201 ms 7580 KB Output is correct
4 Correct 203 ms 7572 KB Output is correct
5 Correct 225 ms 7580 KB Output is correct
6 Correct 204 ms 7564 KB Output is correct
7 Correct 196 ms 7668 KB Output is correct
8 Correct 176 ms 7564 KB Output is correct
9 Correct 197 ms 7576 KB Output is correct
10 Correct 214 ms 7584 KB Output is correct
11 Correct 194 ms 7492 KB Output is correct
12 Correct 228 ms 7464 KB Output is correct
13 Correct 243 ms 7464 KB Output is correct
14 Correct 204 ms 7464 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2572 KB Output is correct
2 Correct 25 ms 2940 KB Output is correct
3 Correct 152 ms 6452 KB Output is correct
4 Correct 188 ms 7564 KB Output is correct
5 Correct 226 ms 7568 KB Output is correct
6 Correct 212 ms 7620 KB Output is correct
7 Correct 192 ms 7564 KB Output is correct
8 Correct 198 ms 7604 KB Output is correct
9 Correct 224 ms 7576 KB Output is correct
10 Correct 210 ms 7660 KB Output is correct
11 Correct 222 ms 7468 KB Output is correct
12 Correct 207 ms 7468 KB Output is correct
13 Correct 210 ms 7472 KB Output is correct
14 Correct 173 ms 7372 KB Output is correct
15 Correct 207 ms 7676 KB Output is correct
16 Correct 168 ms 7580 KB Output is correct
17 Correct 185 ms 7472 KB Output is correct
18 Correct 209 ms 7496 KB Output is correct
19 Correct 183 ms 7596 KB Output is correct
20 Incorrect 197 ms 7340 KB Output is incorrect: {s, t} is wrong.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2984 KB Output is correct
2 Correct 34 ms 3036 KB Output is correct
3 Correct 221 ms 7900 KB Output is correct
4 Correct 248 ms 8036 KB Output is correct
5 Correct 299 ms 8556 KB Output is correct
6 Correct 283 ms 8556 KB Output is correct
7 Correct 315 ms 8544 KB Output is correct
8 Incorrect 299 ms 8552 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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