oj.uz

Submission #1055217

# Submission time Handle Problem Language Result Execution time Memory
1055217 2024-08-12T15:31:22 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
51 / 100
 105 ms 14332 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){
    queue<int> q;
    q.push(0);
    dep[0] = 1;
    while(!q.empty()){
        int f = q.front();q.pop();
        for(auto j:adj[f]){
            if(dep[j.first]==0){
                dep[j.first] = dep[f]+1;
                p[j.first] = {f,j.second};
                q.push(j.first);
            }
        }
    }
}

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:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0;i<U.size();i++){
      |                   ~^~~~~~~~~
highway.cpp:83: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]
   83 |     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 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 8 ms 5720 KB Output is correct
3 Correct 82 ms 13980 KB Output is correct
4 Correct 75 ms 13836 KB Output is correct
5 Correct 79 ms 13852 KB Output is correct
6 Correct 77 ms 13748 KB Output is correct
7 Correct 81 ms 13788 KB Output is correct
8 Correct 81 ms 13936 KB Output is correct
9 Correct 75 ms 13688 KB Output is correct
10 Correct 76 ms 13748 KB Output is correct
11 Correct 92 ms 13740 KB Output is correct
12 Correct 82 ms 13944 KB Output is correct
13 Correct 81 ms 13964 KB Output is correct
14 Correct 76 ms 13944 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5720 KB Output is correct
2 Correct 15 ms 6776 KB Output is correct
3 Correct 23 ms 7368 KB Output is correct
4 Correct 68 ms 13456 KB Output is correct
5 Correct 65 ms 13484 KB Output is correct
6 Correct 64 ms 13488 KB Output is correct
7 Correct 51 ms 13488 KB Output is correct
8 Correct 60 ms 13488 KB Output is correct
9 Correct 56 ms 13436 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 8 ms 5720 KB Output is correct
3 Correct 61 ms 12040 KB Output is correct
4 Correct 92 ms 13744 KB Output is correct
5 Correct 67 ms 13768 KB Output is correct
6 Correct 80 ms 13744 KB Output is correct
7 Correct 73 ms 14000 KB Output is correct
8 Correct 82 ms 13688 KB Output is correct
9 Correct 81 ms 13744 KB Output is correct
10 Correct 97 ms 13780 KB Output is correct
11 Correct 85 ms 13744 KB Output is correct
12 Correct 87 ms 13948 KB Output is correct
13 Correct 81 ms 13744 KB Output is correct
14 Correct 83 ms 13948 KB Output is correct
15 Correct 74 ms 13756 KB Output is correct
16 Correct 70 ms 13780 KB Output is correct
17 Correct 84 ms 13960 KB Output is correct
18 Correct 84 ms 13964 KB Output is correct
19 Correct 81 ms 13744 KB Output is correct
20 Correct 88 ms 13944 KB Output is correct
21 Correct 78 ms 14208 KB Output is correct
22 Correct 70 ms 14216 KB Output is correct
23 Correct 81 ms 14332 KB Output is correct
24 Correct 82 ms 14332 KB Output is correct
25 Correct 105 ms 13780 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 11476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 11476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -