oj.uz

Submission #1016851

# Submission time Handle Problem Language Result Execution time Memory
1016851 2024-07-08T13:30:31 Z Unforgettablepl Highway Tolls (IOI18_highway) C++17
51 / 100
 133 ms 12088 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);
    base = ask(baseask);
    basedep = base/((long long)A);
    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:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
      |                       ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1532 KB Output is correct
3 Correct 88 ms 9596 KB Output is correct
4 Correct 90 ms 9624 KB Output is correct
5 Correct 93 ms 9644 KB Output is correct
6 Correct 75 ms 9612 KB Output is correct
7 Correct 81 ms 9620 KB Output is correct
8 Correct 99 ms 9632 KB Output is correct
9 Correct 84 ms 9680 KB Output is correct
10 Correct 97 ms 9876 KB Output is correct
11 Correct 89 ms 8904 KB Output is correct
12 Correct 88 ms 8916 KB Output is correct
13 Correct 84 ms 9352 KB Output is correct
14 Correct 72 ms 8920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 15 ms 2332 KB Output is correct
3 Correct 20 ms 3416 KB Output is correct
4 Correct 66 ms 8904 KB Output is correct
5 Correct 62 ms 8900 KB Output is correct
6 Correct 61 ms 8904 KB Output is correct
7 Correct 61 ms 8904 KB Output is correct
8 Correct 61 ms 8924 KB Output is correct
9 Correct 60 ms 8900 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1560 KB Output is correct
3 Correct 75 ms 7796 KB Output is correct
4 Correct 84 ms 10060 KB Output is correct
5 Correct 76 ms 9580 KB Output is correct
6 Correct 84 ms 9600 KB Output is correct
7 Correct 81 ms 9620 KB Output is correct
8 Correct 85 ms 9596 KB Output is correct
9 Correct 89 ms 9640 KB Output is correct
10 Correct 88 ms 9684 KB Output is correct
11 Correct 85 ms 8920 KB Output is correct
12 Correct 78 ms 8924 KB Output is correct
13 Correct 81 ms 8904 KB Output is correct
14 Correct 85 ms 8916 KB Output is correct
15 Correct 87 ms 9584 KB Output is correct
16 Correct 81 ms 9740 KB Output is correct
17 Correct 83 ms 8904 KB Output is correct
18 Correct 83 ms 8924 KB Output is correct
19 Correct 81 ms 9652 KB Output is correct
20 Correct 77 ms 8924 KB Output is correct
21 Correct 71 ms 10796 KB Output is correct
22 Correct 82 ms 10668 KB Output is correct
23 Correct 79 ms 10560 KB Output is correct
24 Correct 81 ms 10464 KB Output is correct
25 Correct 82 ms 9064 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1368 KB Output is correct
2 Correct 12 ms 1664 KB Output is correct
3 Correct 107 ms 10176 KB Output is correct
4 Correct 114 ms 10960 KB Output is correct
5 Incorrect 133 ms 12088 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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