oj.uz

Submission #1017068

# Submission time Handle Problem Language Result Execution time Memory
1017068 2024-07-08T20:13:38 Z Unforgettablepl Highway Tolls (IOI18_highway) C++17
51 / 100
 106 ms 10724 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,1));
    auto secbase = (base/B)*A;
    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 secbase==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> depth;
    auto bfs = [&](int x){
        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])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(M,1);
            for(int i=0;i<x;i++)wt[pedge[arr[i].second]]=0;
            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,depthv,pedgev;
    bfs(ue);
    swap(depth,depthu);
    swap(pedge,pedgeu);
    bfs(ve);
    swap(depth,depthv);
    swap(pedge,pedgev);
    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);
    a = getsol(activeu);
    swap(depth,depthv);
    swap(pedge,pedgev);
    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:62: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]
   62 |             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 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 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 1532 KB Output is correct
3 Correct 92 ms 10476 KB Output is correct
4 Correct 97 ms 10232 KB Output is correct
5 Correct 87 ms 10188 KB Output is correct
6 Correct 83 ms 10176 KB Output is correct
7 Correct 91 ms 10260 KB Output is correct
8 Correct 84 ms 10504 KB Output is correct
9 Correct 95 ms 10276 KB Output is correct
10 Correct 86 ms 10312 KB Output is correct
11 Correct 92 ms 9396 KB Output is correct
12 Correct 93 ms 9668 KB Output is correct
13 Correct 91 ms 9596 KB Output is correct
14 Correct 96 ms 9920 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 2320 KB Output is correct
3 Correct 19 ms 3420 KB Output is correct
4 Correct 66 ms 9164 KB Output is correct
5 Correct 67 ms 9168 KB Output is correct
6 Correct 79 ms 9704 KB Output is correct
7 Correct 67 ms 9652 KB Output is correct
8 Correct 75 ms 9264 KB Output is correct
9 Correct 67 ms 9696 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 10 ms 1272 KB Output is correct
3 Correct 69 ms 8036 KB Output is correct
4 Correct 92 ms 10112 KB Output is correct
5 Correct 106 ms 10440 KB Output is correct
6 Correct 87 ms 10180 KB Output is correct
7 Correct 88 ms 10188 KB Output is correct
8 Correct 86 ms 10168 KB Output is correct
9 Correct 97 ms 10224 KB Output is correct
10 Correct 101 ms 10204 KB Output is correct
11 Correct 91 ms 9680 KB Output is correct
12 Correct 93 ms 9692 KB Output is correct
13 Correct 104 ms 9684 KB Output is correct
14 Correct 97 ms 9184 KB Output is correct
15 Correct 84 ms 10136 KB Output is correct
16 Correct 86 ms 10196 KB Output is correct
17 Correct 97 ms 9796 KB Output is correct
18 Correct 100 ms 9588 KB Output is correct
19 Correct 78 ms 10380 KB Output is correct
20 Correct 92 ms 9552 KB Output is correct
21 Correct 80 ms 10724 KB Output is correct
22 Correct 87 ms 10344 KB Output is correct
23 Correct 83 ms 10000 KB Output is correct
24 Correct 85 ms 10220 KB Output is correct
25 Correct 97 ms 9768 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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