oj.uz

Submission #115520

# Submission time Handle Problem Language Result Execution time Memory
115520 2019-06-08T04:00:33 Z onjo0127 Highway Tolls (IOI18_highway) C++11
12 / 100
 411 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<pii> adj[90009];
int dep[90009], pid[90009];

void go(int x, int p, int d, int id) {
    dep[x] = d; pid[x] = id;
    for(auto& it: adj[x]) if(it.first != p) go(it.first, x, d+1, it.second);
}

void solveRoot(int N, vector<int> U, vector<int> V, int A, int B, int root) {
    int 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});
    }
    go(root, root, 0, -1);
    vector<int> W(M, 0); long long gi = ask(W);
    int l = 1, r = N-1;
    while(l <= r) {
        W = vector<int>(M, 0);
        int m = l+r >> 1;
        for(int i=0; i<N; i++) {
            if(dep[i] >= m) W[pid[i]] = 1;
        }
        long long t = ask(W);
        if(t != gi) l = m+1;
        else r = m-1;
    }
    vector<int> P;
    for(int i=0; i<N; i++) if(dep[i] == r) P.push_back(i);
    while((int)P.size() > 1) {
        vector<int> NP;
        W = vector<int>(M, 0);
        for(int i=0; i<(int)P.size()/2; i++) W[pid[P[i]]] = 1;
        long long t = ask(W);
        if(t != gi) for(int i=0; i<(int)P.size()/2; i++) NP.push_back(P[i]);
        else for(int i=(int)P.size()/2; i<P.size(); i++) NP.push_back(P[i]);
        P = NP;
    }
    answer(root, P[0]);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    solveRoot(N, U, V, A, B, 0);
}

Compilation message

highway.cpp: In function 'void solveRoot(int, std::vector<int>, std::vector<int>, int, int, int)':
highway.cpp:25:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l+r >> 1;
                 ~^~
highway.cpp:41:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else for(int i=(int)P.size()/2; i<P.size(); i++) NP.push_back(P[i]);
                                         ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:9: warning: unused variable 'M' [-Wunused-variable]
     int M = U.size();
         ^

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 2436 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Correct 4 ms 2444 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2344 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2344 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 2552 KB Output is correct
2 Correct 25 ms 3208 KB Output is correct
3 Correct 192 ms 9484 KB Output is correct
4 Correct 183 ms 9600 KB Output is correct
5 Correct 215 ms 9600 KB Output is correct
6 Correct 159 ms 9704 KB Output is correct
7 Correct 190 ms 9660 KB Output is correct
8 Correct 167 ms 9700 KB Output is correct
9 Correct 194 ms 9712 KB Output is correct
10 Correct 182 ms 9824 KB Output is correct
11 Correct 230 ms 10080 KB Output is correct
12 Correct 193 ms 10256 KB Output is correct
13 Correct 185 ms 10180 KB Output is correct
14 Correct 187 ms 9500 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3576 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 2472 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 Runtime error 411 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 380 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -