oj.uz

Submission #120286

# Submission time Handle Problem Language Result Execution time Memory
120286 2019-06-24T06:38:22 Z 이온조(#2949) Highway Tolls (IOI18_highway) C++14
0 / 100
 35 ms 3304 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, M;
long long ori;
vector<pii> adj[90009];
int D[90009];

int any(vector<int> S) {
    int K = S.size();
    int l = 0, r = K-1;
    while(l <= r) {
        if(l == r) return S[l];
        int m = l+r >> 1;
        vector<int> W(M, 0);
        for(int i=0; i<=m; i++) for(auto& it: adj[S[i]]) W[it.second] = 1;
        if(ask(W) != ori) r = m-1;
        else l = m+1;
    }
    return S[r+1];
}

vector<int> f(int root) {
    int c = 1;
    for(int i=0; i<n; i++) D[i] = 0;
    queue<int> que; que.push(root); D[root] = 1;
    while(que.size()) {
        int sz = que.size();
        while(sz--) {
            int now; now = que.front(); que.pop();
            for(auto& it: adj[now]) {
                if(!D[it.first]) {
                    D[it.first] = c+1;
                    que.push(it.first);
                }
            }
        }
        ++c;
    }
    vector<int> S;
    for(int i=0; i<n; i++) S.push_back(i);
    sort(S.begin(), S.end(), [&](int P, int Q) {return D[P] > D[Q];});
    return S;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N; M = U.size();
    for(int i=0; i<M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vector<int> W(M, 0), S = f(0); ori = ask(W);
    reverse(S.begin(), S.end());
    int P = any(f(any(S)));
    int Q = any(f(P));
    answer(P, Q);
}

Compilation message

highway.cpp: In function 'int any(std::vector<int>)':
highway.cpp:16:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 5 ms 2424 KB Output is correct
3 Incorrect 4 ms 2324 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3172 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 5 ms 2552 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 21 ms 3304 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 35 ms 3280 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -