oj.uz

Submission #1055208

# Submission time Handle Problem Language Result Execution time Memory
1055208 2024-08-12T15:25:29 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
51 / 100
 198 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);
    if(ans3==-1){
        assert(0);
    }
    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 4692 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 4708 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 73 ms 13684 KB Output is correct
4 Correct 65 ms 13744 KB Output is correct
5 Correct 69 ms 13684 KB Output is correct
6 Correct 72 ms 13900 KB Output is correct
7 Correct 82 ms 13744 KB Output is correct
8 Correct 70 ms 13744 KB Output is correct
9 Correct 73 ms 13688 KB Output is correct
10 Correct 73 ms 13744 KB Output is correct
11 Correct 80 ms 14968 KB Output is correct
12 Correct 81 ms 15280 KB Output is correct
13 Correct 81 ms 15024 KB Output is correct
14 Correct 71 ms 14452 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6232 KB Output is correct
2 Correct 14 ms 7632 KB Output is correct
3 Correct 23 ms 8656 KB Output is correct
4 Correct 59 ms 17584 KB Output is correct
5 Correct 63 ms 17584 KB Output is correct
6 Correct 58 ms 17584 KB Output is correct
7 Correct 53 ms 17524 KB Output is correct
8 Correct 60 ms 17528 KB Output is correct
9 Correct 72 ms 17584 KB Output is correct

Subtask #4
33.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 73 ms 12212 KB Output is correct
4 Correct 80 ms 13684 KB Output is correct
5 Correct 67 ms 13744 KB Output is correct
6 Correct 81 ms 13756 KB Output is correct
7 Correct 82 ms 13812 KB Output is correct
8 Correct 90 ms 13752 KB Output is correct
9 Correct 85 ms 13688 KB Output is correct
10 Correct 82 ms 13744 KB Output is correct
11 Correct 90 ms 14512 KB Output is correct
12 Correct 106 ms 15492 KB Output is correct
13 Correct 91 ms 15024 KB Output is correct
14 Correct 80 ms 15224 KB Output is correct
15 Correct 73 ms 13688 KB Output is correct
16 Correct 86 ms 13744 KB Output is correct
17 Correct 93 ms 14996 KB Output is correct
18 Correct 84 ms 14728 KB Output is correct
19 Correct 80 ms 13688 KB Output is correct
20 Correct 85 ms 15740 KB Output is correct
21 Correct 72 ms 14212 KB Output is correct
22 Correct 68 ms 14196 KB Output is correct
23 Correct 79 ms 13480 KB Output is correct
24 Correct 82 ms 13936 KB Output is correct
25 Correct 99 ms 17288 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 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 198 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -