Submission #1055154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1055154	2024-08-12T14:59:53 Z	Ahmed57	Highway Tolls (IOI18_highway)	C++17	5 / 100	188 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==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 = -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:74: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]
   74 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

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	3632 KB	Output is correct
3	Correct	75 ms	10488 KB	Output is correct
4	Correct	79 ms	10388 KB	Output is correct
5	Correct	66 ms	10428 KB	Output is correct
6	Correct	67 ms	10388 KB	Output is correct
7	Correct	79 ms	10488 KB	Output is correct
8	Correct	74 ms	10384 KB	Output is correct
9	Correct	69 ms	10492 KB	Output is correct
10	Correct	76 ms	10428 KB	Output is correct
11	Correct	74 ms	11188 KB	Output is correct
12	Correct	75 ms	11300 KB	Output is correct
13	Correct	80 ms	11008 KB	Output is correct
14	Runtime error	77 ms	20944 KB	Execution killed with signal 6
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3928 KB	Output is correct
2	Correct	12 ms	5372 KB	Output is correct
3	Correct	21 ms	6476 KB	Output is correct
4	Correct	60 ms	14140 KB	Output is correct
5	Correct	69 ms	14064 KB	Output is correct
6	Correct	61 ms	14072 KB	Output is correct
7	Correct	58 ms	14092 KB	Output is correct
8	Correct	72 ms	14064 KB	Output is correct
9	Incorrect	58 ms	14072 KB	Output is incorrect: {s, t} is wrong.
10	Halted	0 ms	0 KB	-