oj.uz

Submission #1017057

# Submission time Handle Problem Language Result Execution time Memory
1017057 2024-07-08T19:44:56 Z Unforgettablepl Highway Tolls (IOI18_highway) C++17
51 / 100
 158 ms 13556 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);
    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);
    }
    auto base = ask(vector<int>(M));
    int pathver = 0;
    int ue = 0;
    int ve = 0;
    {
        auto check = [&](int x){
            vector<int> a(M);
            for(int i=0;i<x;i++)a[i]=1;
            return base==ask(a);
        };
        for(int jump = 65536;jump;jump/=2){
            if(pathver+jump>=M)continue;
            if(check(pathver+jump))pathver+=jump;
        }
        ue = U[pathver];
        ve = V[pathver];
    }
    vector<int> pedge;
    vector<int> baseask;
    vector<int> depth;
    auto bfs = [&](int x){
        baseask = vector<int>(M);
        depth = vector<int>(N);
        pedge = vector<int>(N);
        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);
        }
    };
    auto getsol = [&](vector<bool> activeidx){
        vector<pair<int,int>> arr;
        for(int i=0;i<N;i++)if(activeidx[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>=arr.size())continue;
            if(check(st+jump))st+=jump;
        }
        return arr[st].second;
    };
    vector<int> depthu,pedgeu,baseasku,depthv,pedgev,baseaskv;
    bfs(ue);
    swap(depth,depthu);
    swap(pedge,pedgeu);
    swap(baseask,baseasku);
    bfs(ve);
    swap(depth,depthv);
    swap(pedge,pedgev);
    swap(baseask,baseaskv);
    int a,b;
    vector<bool> activeu(N),activev(N);
    for(int i=0;i<N;i++){
        if(depthu[i]<depthv[i])activeu[i]=true;
        else if(depthu[i]>depthv[i])activev[i]=true;
    }
    swap(depth,depthu);
    swap(pedge,pedgeu);
    swap(baseask,baseasku);
    a = getsol(activeu);
    swap(depth,depthv);
    swap(pedge,pedgev);
    swap(baseask,baseaskv);
    b = getsol(activev);
    answer(a,b);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp: In lambda function:
highway.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if(st+jump>=arr.size())continue;
      |                ~~~~~~~^~~~~~~~~~~~

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 1 ms 344 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 0 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 9 ms 1676 KB Output is correct
3 Correct 86 ms 11004 KB Output is correct
4 Correct 95 ms 11188 KB Output is correct
5 Correct 90 ms 10992 KB Output is correct
6 Correct 88 ms 11128 KB Output is correct
7 Correct 93 ms 10944 KB Output is correct
8 Correct 98 ms 11020 KB Output is correct
9 Correct 76 ms 10964 KB Output is correct
10 Correct 95 ms 11000 KB Output is correct
11 Correct 94 ms 10092 KB Output is correct
12 Correct 96 ms 10460 KB Output is correct
13 Correct 90 ms 10256 KB Output is correct
14 Correct 91 ms 10452 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 19 ms 2392 KB Output is correct
3 Correct 22 ms 3736 KB Output is correct
4 Correct 66 ms 9780 KB Output is correct
5 Correct 66 ms 9884 KB Output is correct
6 Correct 66 ms 10316 KB Output is correct
7 Correct 63 ms 10216 KB Output is correct
8 Correct 70 ms 10388 KB Output is correct
9 Correct 62 ms 10236 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 12 ms 1368 KB Output is correct
3 Correct 64 ms 8516 KB Output is correct
4 Correct 94 ms 10968 KB Output is correct
5 Correct 79 ms 10916 KB Output is correct
6 Correct 82 ms 10968 KB Output is correct
7 Correct 80 ms 11004 KB Output is correct
8 Correct 86 ms 10960 KB Output is correct
9 Correct 96 ms 10996 KB Output is correct
10 Correct 94 ms 10968 KB Output is correct
11 Correct 106 ms 10228 KB Output is correct
12 Correct 92 ms 10440 KB Output is correct
13 Correct 103 ms 10220 KB Output is correct
14 Correct 97 ms 9920 KB Output is correct
15 Correct 84 ms 10996 KB Output is correct
16 Correct 76 ms 11000 KB Output is correct
17 Correct 91 ms 10452 KB Output is correct
18 Correct 81 ms 10448 KB Output is correct
19 Correct 80 ms 10924 KB Output is correct
20 Correct 75 ms 10216 KB Output is correct
21 Correct 74 ms 11088 KB Output is correct
22 Correct 82 ms 11108 KB Output is correct
23 Correct 83 ms 10712 KB Output is correct
24 Correct 82 ms 10912 KB Output is correct
25 Correct 95 ms 10584 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1624 KB Output is correct
2 Correct 10 ms 1624 KB Output is correct
3 Correct 106 ms 11412 KB Output is correct
4 Correct 122 ms 11680 KB Output is correct
5 Correct 134 ms 13076 KB Output is correct
6 Correct 154 ms 13052 KB Output is correct
7 Correct 146 ms 13172 KB Output is correct
8 Incorrect 158 ms 13308 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1624 KB Output is correct
2 Correct 10 ms 1624 KB Output is correct
3 Correct 100 ms 11160 KB Output is correct
4 Correct 100 ms 11616 KB Output is correct
5 Correct 123 ms 11760 KB Output is correct
6 Correct 138 ms 12972 KB Output is correct
7 Correct 105 ms 11592 KB Output is correct
8 Correct 101 ms 11772 KB Output is correct
9 Correct 118 ms 11500 KB Output is correct
10 Correct 138 ms 13556 KB Output is correct
11 Correct 123 ms 13176 KB Output is correct
12 Correct 135 ms 12972 KB Output is correct
13 Incorrect 104 ms 11340 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -