oj.uz

Submission #1055495

# Submission time Handle Problem Language Result Execution time Memory
1055495 2024-08-12T20:09:35 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
12 / 100
 86 ms 14320 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>> v;
vector<pair<int,int>> adj[100001];
void dfs(int i){
    queue<int> q;
    q.push(0);
    dep[0] = 1;
    p[0] = {0,-1};
    while(!q.empty()){
        int f = q.front();q.pop();
        v.push_back({dep[f],f});
        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();
    int n = N;
    vector<int32_t> as(m,0);
    int len = ask(as);
    for(int i = 0;i<U.size();i++){
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    int l = 0 ,r = n-1 , ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,0);
        for(int i = mid+1;i<n;i++){
            for(auto j:adj[i]){
                as[j.second] = 1;
            }
        }
        if(ask(as)==len){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    dfs(ans);
    
    l = 1 , r = n-1 ;int ans2 = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,1);
        for(int i = 1;i<=mid;i++){
            as[p[v[i].second].second] =0 ;
        }
        if(ask(as)==len){
            ans2 = mid;
            r = mid-1;
        }else l = mid+1;
    }
    int a = v[ans2].second;
    l = 0 , r = ans2-1 ;
    int ans3 = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,1);
        for(int i = 1;i<=mid;i++){
            as[p[v[i].second].second] = 0;
        }
        int f = a;
        while(p[f].second!=-1){
            as[p[f].second] = 0;
            f = p[f].first;
        }
        if(ask(as)==len){
            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(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:33:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0;i<U.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 2728 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 10 ms 4028 KB Output is correct
3 Correct 78 ms 13624 KB Output is correct
4 Correct 82 ms 14204 KB Output is correct
5 Correct 79 ms 13616 KB Output is correct
6 Correct 80 ms 13744 KB Output is correct
7 Correct 78 ms 13696 KB Output is correct
8 Correct 73 ms 13752 KB Output is correct
9 Correct 69 ms 13804 KB Output is correct
10 Correct 83 ms 13676 KB Output is correct
11 Correct 78 ms 13808 KB Output is correct
12 Correct 86 ms 13716 KB Output is correct
13 Correct 81 ms 14320 KB Output is correct
14 Correct 83 ms 13824 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3928 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 10 ms 3928 KB Output is correct
3 Correct 56 ms 11596 KB Output is correct
4 Correct 84 ms 13616 KB Output is correct
5 Incorrect 74 ms 13840 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 4184 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4184 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -