Submission #1055207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1055207	2024-08-12T15:24:18 Z	Ahmed57	Highway Tolls (IOI18_highway)	C++17	18 / 100	201 ms	262144 KB

highway

#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].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);
    if(ans3==-1){
        int x = len/A;
        int b = a;
        while(x--){
            b = p[b].first;
        }
        answer(a,b);
        return ;
    }
    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	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	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	78 ms	13692 KB	Output is correct
4	Correct	70 ms	13828 KB	Output is correct
5	Correct	86 ms	13744 KB	Output is correct
6	Correct	66 ms	13744 KB	Output is correct
7	Correct	76 ms	13744 KB	Output is correct
8	Correct	72 ms	13744 KB	Output is correct
9	Correct	72 ms	13812 KB	Output is correct
10	Correct	75 ms	13688 KB	Output is correct
11	Correct	83 ms	14732 KB	Output is correct
12	Correct	82 ms	15472 KB	Output is correct
13	Correct	78 ms	14984 KB	Output is correct
14	Correct	74 ms	14512 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6232 KB	Output is correct
2	Correct	13 ms	7632 KB	Output is correct
3	Correct	19 ms	8648 KB	Output is correct
4	Correct	62 ms	17528 KB	Output is correct
5	Correct	55 ms	17532 KB	Output is correct
6	Correct	60 ms	17528 KB	Output is correct
7	Correct	65 ms	17544 KB	Output is correct
8	Correct	63 ms	17588 KB	Output is correct
9	Correct	59 ms	17580 KB	Output is correct