Submission #1055140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1055140	2024-08-12T14:52:01 Z	Ahmed57	Highway Tolls (IOI18_highway)	C++17	5 / 100	196 ms	262144 KB

highway

#include "bits/stdc++.h"
#include "highway.h"

using namespace std;
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(int N, vector<int> U, vector<int> V, int A, int B){
    int m = U.size();
    vector<int> as(m,0);
    vector<int> 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<int> 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<int> 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>len+(dep[a]-mid+1)*(B-A)){
            ans2 = mid;
            l = mid+1;
        }else r = mid-1;
    }
    if(ans2==-1){
        int x = len/A;
        int b = a;
        while(x--){
            b = p[b].first;
        }
        answer(a,b);
        return ;
    }
    vector<int> lol;
    l = -1;
    for(int i = 0;i<v.size();i++){
        if(v[i].first==ans2&&l==-1)l = i;
        if(v[i].first==ans2)r = i;
    }   
    int ans3 = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int> as(m,0);
        for(int i = 0;i<=mid;i++){
            as[p[v[i].second].second] = 1;
        }
        if(ask(as)==len+(dep[a]-ans2+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(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0;i<U.size();i++){
      |                   ~^~~~~~~~~
highway.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
highway.cpp:22:9: warning: unused variable 'len2' [-Wunused-variable]
   22 |     int len2 = ask(as2);
      |         ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	8 ms	3636 KB	Output is correct
3	Correct	73 ms	10512 KB	Output is correct
4	Correct	70 ms	10880 KB	Output is correct
5	Correct	68 ms	10384 KB	Output is correct
6	Correct	63 ms	10392 KB	Output is correct
7	Correct	83 ms	10496 KB	Output is correct
8	Correct	73 ms	10392 KB	Output is correct
9	Correct	65 ms	10396 KB	Output is correct
10	Correct	70 ms	10424 KB	Output is correct
11	Correct	75 ms	10888 KB	Output is correct
12	Correct	76 ms	11444 KB	Output is correct
13	Correct	72 ms	11016 KB	Output is correct
14	Incorrect	70 ms	10536 KB	Output is incorrect: {s, t} is wrong.
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4184 KB	Output is correct
2	Correct	13 ms	5364 KB	Output is correct
3	Correct	19 ms	6580 KB	Output is correct
4	Correct	57 ms	14124 KB	Output is correct
5	Correct	54 ms	14072 KB	Output is correct
6	Correct	59 ms	14076 KB	Output is correct
7	Correct	69 ms	14068 KB	Output is correct
8	Correct	56 ms	14068 KB	Output is correct
9	Incorrect	70 ms	14004 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-