oj.uz

Submission #1055203

# Submission time Handle Problem Language Result Execution time Memory
1055203 2024-08-12T15:21:40 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
18 / 100
 194 ms 262144 KB 
#include "bits/stdc++.h"
#include "highway.h"

using namespace std;
#define int long long
pair<int,int> p[100001];
int dep[100001];
vector<pair<int,int>> adj[100001];
void dfs(int i,int pr,int id){
    dep[i] = dep[pr]+1;
    p[i] = {pr,id};
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        dfs(j.first,i,j.second);
    }
}

void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B){
    int m = U.size();
    vector<int32_t> as(m,0);
    vector<int32_t> as2(m,1);
    int len = ask(as);
    int len2 = ask(as2);
    for(int i = 0;i<U.size();i++){
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    dfs(0,0,-1);
    vector<pair<int,int>> v;
    for(int i = 0;i<N;i++){
        v.push_back({dep[i],i});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int l = 0 , r = v.size()-2 , ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,0);
        for(int i = 0;i<=mid;i++){
            as[p[v[i].second].second] = 1;
        }
        if(ask(as)!=len){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    int a = v[ans].second;
    l = 2 , r = dep[a] ;int ans2 = -1; 
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,0);
        for(int i = 0;i<N;i++){
            if(dep[i]>=mid){
                as[p[i].second] =1 ;
            }
        }
        int na = ask(as);
        if(na==len2){
            ans2 = mid;
            l = mid+1;
        }else r = mid-1;
    }
    assert(ans2!=-1);
    ans2--;
    if((dep[a]-ans2)*A==len){
        int x = len/A;
        int b = a;
        while(x--){
            b = p[b].first;
        }
        answer(a,b);
        return ;
    }
    vector<int> lol;
    l = 0;
    for(int i = 0;i<v.size();i++){
        if(v[i].second==a)l = i;
        if(v[i].first>ans2)r = i;
    }   
    int ans3 = -1;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,0);
        for(int i = 0;i<=mid;i++){
            as[p[v[i].second].second] = 1;
        }
        int f = a;
        while(dep[f]>v[mid].first)f = p[f].first;
        as[p[f].second] = 1;
        if(ask(as)==len+(dep[a]-v[mid].first+1)*(B-A)+(B-A)){
            ans3 = mid;
            r = mid-1;
        }else l = mid+1;
    }
    //assert(ans3!=-1);
    int b = v[ans3].second;
    answer(a,b);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 4692 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 7 ms 5720 KB Output is correct
3 Correct 75 ms 13696 KB Output is correct
4 Correct 73 ms 13712 KB Output is correct
5 Correct 75 ms 13752 KB Output is correct
6 Correct 76 ms 13744 KB Output is correct
7 Correct 73 ms 13868 KB Output is correct
8 Correct 74 ms 13708 KB Output is correct
9 Correct 70 ms 13744 KB Output is correct
10 Correct 74 ms 13740 KB Output is correct
11 Correct 77 ms 15020 KB Output is correct
12 Correct 83 ms 15220 KB Output is correct
13 Correct 76 ms 14852 KB Output is correct
14 Correct 75 ms 14512 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6484 KB Output is correct
2 Correct 13 ms 7540 KB Output is correct
3 Correct 20 ms 8648 KB Output is correct
4 Correct 61 ms 17524 KB Output is correct
5 Correct 59 ms 17592 KB Output is correct
6 Correct 58 ms 17536 KB Output is correct
7 Correct 59 ms 17584 KB Output is correct
8 Correct 54 ms 17536 KB Output is correct
9 Correct 58 ms 17584 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 9 ms 5720 KB Output is correct
3 Correct 62 ms 12256 KB Output is correct
4 Incorrect 79 ms 13832 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 194 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -