oj.uz

답안 #115520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115520 2019-06-08T04:00:33 Z onjo0127 통행료 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -