oj.uz

Submission #1055191

# Submission time Handle Problem Language Result Execution time Memory
1055191 2024-08-12T15:14:27 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
18 / 100
 190 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;
    }
    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 = 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;
        }
        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;
    }
    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:75: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]
   75 |     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 4696 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 4700 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 9 ms 5820 KB Output is correct
3 Correct 78 ms 13704 KB Output is correct
4 Correct 68 ms 13692 KB Output is correct
5 Correct 72 ms 13696 KB Output is correct
6 Correct 69 ms 13744 KB Output is correct
7 Correct 81 ms 13748 KB Output is correct
8 Correct 85 ms 13744 KB Output is correct
9 Correct 69 ms 13744 KB Output is correct
10 Correct 79 ms 13828 KB Output is correct
11 Correct 76 ms 14736 KB Output is correct
12 Correct 84 ms 15236 KB Output is correct
13 Correct 82 ms 15028 KB Output is correct
14 Correct 75 ms 14460 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6232 KB Output is correct
2 Correct 13 ms 7632 KB Output is correct
3 Correct 20 ms 8656 KB Output is correct
4 Correct 64 ms 17532 KB Output is correct
5 Correct 74 ms 17584 KB Output is correct
6 Correct 59 ms 17584 KB Output is correct
7 Correct 61 ms 17584 KB Output is correct
8 Correct 55 ms 17536 KB Output is correct
9 Correct 57 ms 17544 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 8 ms 5720 KB Output is correct
3 Correct 59 ms 12004 KB Output is correct
4 Incorrect 85 ms 13692 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 190 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 178 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -