oj.uz

답안 #1016844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016844 2024-07-08T13:21:44 Z Unforgettablepl 통행료 (IOI18_highway) C++17
51 / 100
 121 ms 10836 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(),x.end()
 
long long ask(const std::vector<int> &w);
void answer(int s, int t);
 
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    vector<vector<pair<int,int>>> adj(N);
    vector<int> baseask;
    int M = U.size();
    for(int i=0;i<U.size();i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    vector<int> pedge(N);
    vector<int> depth(N);
    auto bfs = [&](int x){
        baseask = vector<int>(M);
        queue<tuple<int,int,int,int>> q;
        q.emplace(0,-1,x,-1);
        vector<bool> visited(N);
        while(!q.empty()){
            auto [dep,par,idx,actpar] = q.front();q.pop();
            if(visited[idx]){
                baseask[par]=1;
                continue;
            }
            visited[idx]=true;
            pedge[idx]=par;
            depth[idx]=dep;
            for(auto[v,i]:adj[idx])if(v!=actpar)q.emplace(dep+1,i,v,idx);
        }
    };
    bfs(0);
    auto base = ask(baseask);
    auto basedep = base/((long long)A);
    // Calculate st
    vector<pair<int,int>> arr;
    for(int i=0;i<N;i++)arr.emplace_back(depth[i],i);
    sort(arr.rbegin(),arr.rend());
    auto check = [&](int x){
        vector<int> wt = baseask;
        for(int i=0;i<x;i++)wt[pedge[arr[i].second]]=1;
        return base==ask(wt);
    };
    int st = 0;
    for(int jump = 65536;jump;jump/=2){
        if(st+jump>=N)continue;
        if(check(st+jump))st+=jump;
    }
    st = arr[st].second;
    bfs(st);
    vector<int> sus;
    for(int i=0;i<N;i++)if(depth[i]==basedep)sus.emplace_back(i);
    while(sus.size()>1){
        int mid = (sus.size())/2;
        vector<int> left,right;
        for(int i=0;i<mid;i++)left.emplace_back(sus[i]);
        for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
        vector<int> w = baseask;
        for(int&i:left)w[pedge[i]]=1;
        auto ans = ask(w);
        if(ans!=base)sus=left;
        else sus=right;
    }
    answer(st, sus[0]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
      |                       ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 9 ms 1368 KB Output is correct
3 Correct 121 ms 9592 KB Output is correct
4 Correct 88 ms 9612 KB Output is correct
5 Correct 103 ms 9636 KB Output is correct
6 Correct 93 ms 9840 KB Output is correct
7 Correct 84 ms 9616 KB Output is correct
8 Correct 96 ms 9660 KB Output is correct
9 Correct 76 ms 9740 KB Output is correct
10 Correct 94 ms 9632 KB Output is correct
11 Correct 84 ms 8916 KB Output is correct
12 Correct 86 ms 8928 KB Output is correct
13 Correct 81 ms 8920 KB Output is correct
14 Correct 72 ms 8908 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1276 KB Output is correct
2 Correct 14 ms 2384 KB Output is correct
3 Correct 24 ms 3160 KB Output is correct
4 Correct 71 ms 8904 KB Output is correct
5 Correct 63 ms 8940 KB Output is correct
6 Correct 64 ms 8912 KB Output is correct
7 Correct 60 ms 9176 KB Output is correct
8 Correct 59 ms 9160 KB Output is correct
9 Correct 59 ms 8920 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct
3 Correct 61 ms 7776 KB Output is correct
4 Correct 86 ms 9564 KB Output is correct
5 Correct 89 ms 9576 KB Output is correct
6 Correct 92 ms 9612 KB Output is correct
7 Correct 84 ms 9864 KB Output is correct
8 Correct 80 ms 9592 KB Output is correct
9 Correct 87 ms 9668 KB Output is correct
10 Correct 105 ms 9756 KB Output is correct
11 Correct 82 ms 8904 KB Output is correct
12 Correct 90 ms 8908 KB Output is correct
13 Correct 91 ms 9160 KB Output is correct
14 Correct 81 ms 8904 KB Output is correct
15 Correct 80 ms 9592 KB Output is correct
16 Correct 70 ms 10056 KB Output is correct
17 Correct 77 ms 8904 KB Output is correct
18 Correct 83 ms 8980 KB Output is correct
19 Correct 83 ms 9828 KB Output is correct
20 Correct 93 ms 8904 KB Output is correct
21 Correct 74 ms 10820 KB Output is correct
22 Correct 76 ms 10836 KB Output is correct
23 Correct 90 ms 10340 KB Output is correct
24 Correct 79 ms 10220 KB Output is correct
25 Correct 90 ms 9140 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1568 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1596 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -