oj.uz

Submission #78808

# Submission time Handle Problem Language Result Execution time Memory
78808 2018-10-09T04:14:31 Z wleung_bvg Highway Tolls (IOI18_highway) C++14
12 / 100
 213 ms 7876 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), verts;
    ll DA = ask(Q);
    fill(vis, vis + N, false);
    queue<int> q;
    q.push(0);
    vis[0] = 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;
    }
    answer(0, verts[hi]);
}

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 2412 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2348 KB Output is correct
6 Correct 4 ms 2444 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 2344 KB Output is correct
11 Correct 5 ms 2424 KB Output is correct
12 Correct 4 ms 2344 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 30 ms 3072 KB Output is correct
3 Correct 167 ms 7816 KB Output is correct
4 Correct 188 ms 7760 KB Output is correct
5 Correct 202 ms 7748 KB Output is correct
6 Correct 211 ms 7772 KB Output is correct
7 Correct 169 ms 7836 KB Output is correct
8 Correct 195 ms 7752 KB Output is correct
9 Correct 212 ms 7812 KB Output is correct
10 Correct 178 ms 7876 KB Output is correct
11 Correct 213 ms 7668 KB Output is correct
12 Correct 213 ms 7744 KB Output is correct
13 Correct 198 ms 7752 KB Output is correct
14 Correct 185 ms 7740 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3056 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 Incorrect 4 ms 2424 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.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 -