oj.uz

Submission #78810

# Submission time Handle Problem Language Result Execution time Memory
78810 2018-10-09T04:20:40 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
12 / 100
 307 ms 9104 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];
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) {
        vector<int> verts;
        fill(vis, vis + N, false);
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        while (!q.empty()) {
            int v = q.front();
            verts.pb(v);
            q.pop();
            FORE(w, adj[v]) {
                if (vis[w]) continue;
                vis[w] = 1;
                q.push(w);
            }
        }
        int lo = 0, hi = sz(verts) - 1, mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            FOR(i, mid) vis[verts[i]] = 0;
            For(i, mid, N) vis[verts[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 = verts[hi]);
    }
    answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 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 2324 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2520 KB Output is correct
7 Correct 4 ms 2432 KB Output is correct
8 Correct 4 ms 2440 KB Output is correct
9 Correct 4 ms 2436 KB Output is correct
10 Correct 4 ms 2440 KB Output is correct
11 Correct 4 ms 2524 KB Output is correct
12 Correct 4 ms 2520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 15 ms 3020 KB Output is correct
3 Correct 206 ms 8108 KB Output is correct
4 Correct 218 ms 8092 KB Output is correct
5 Correct 240 ms 8080 KB Output is correct
6 Correct 213 ms 8100 KB Output is correct
7 Correct 206 ms 8100 KB Output is correct
8 Correct 205 ms 8208 KB Output is correct
9 Correct 222 ms 8092 KB Output is correct
10 Correct 233 ms 8200 KB Output is correct
11 Correct 220 ms 7896 KB Output is correct
12 Correct 211 ms 7884 KB Output is correct
13 Correct 233 ms 7880 KB Output is correct
14 Correct 215 ms 7888 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 2984 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 5 ms 2568 KB Output is correct
2 Correct 23 ms 3072 KB Output is correct
3 Correct 171 ms 6956 KB Output is correct
4 Correct 199 ms 8092 KB Output is correct
5 Correct 227 ms 8080 KB Output is correct
6 Correct 188 ms 8088 KB Output is correct
7 Correct 194 ms 8100 KB Output is correct
8 Correct 177 ms 8092 KB Output is correct
9 Correct 208 ms 8088 KB Output is correct
10 Correct 214 ms 8104 KB Output is correct
11 Correct 189 ms 7980 KB Output is correct
12 Correct 211 ms 7892 KB Output is correct
13 Correct 238 ms 7988 KB Output is correct
14 Correct 207 ms 7988 KB Output is correct
15 Correct 207 ms 8088 KB Output is correct
16 Correct 188 ms 8148 KB Output is correct
17 Correct 207 ms 7976 KB Output is correct
18 Correct 211 ms 7984 KB Output is correct
19 Correct 199 ms 8140 KB Output is correct
20 Incorrect 240 ms 7884 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 34 ms 3104 KB Output is correct
2 Correct 18 ms 3112 KB Output is correct
3 Correct 217 ms 8316 KB Output is correct
4 Correct 260 ms 8568 KB Output is correct
5 Correct 289 ms 9076 KB Output is correct
6 Correct 288 ms 9104 KB Output is correct
7 Correct 300 ms 9088 KB Output is correct
8 Incorrect 307 ms 9064 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 3032 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -