oj.uz

Submission #1055494

# Submission time Handle Problem Language Result Execution time Memory
1055494 2024-08-12T20:07:18 Z Ahmed57 Highway Tolls (IOI18_highway) C++17
12 / 100
 97 ms 13904 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){
    queue<int> q;
    q.push(0);
    dep[0] = 1;
    p[0] = {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();
    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);
    vector<pair<int,int>> v;
    for(int i = 0;i<N;i++){
        v.push_back({dep[i],i});
    }
    sort(v.begin(),v.end());
    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: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++){
      |                   ~^~~~~~~~~

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 2 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 8 ms 4052 KB Output is correct
3 Correct 85 ms 13704 KB Output is correct
4 Correct 85 ms 13864 KB Output is correct
5 Correct 86 ms 13800 KB Output is correct
6 Correct 84 ms 13860 KB Output is correct
7 Correct 79 ms 13688 KB Output is correct
8 Correct 86 ms 13864 KB Output is correct
9 Correct 74 ms 13880 KB Output is correct
10 Correct 85 ms 13836 KB Output is correct
11 Correct 84 ms 13672 KB Output is correct
12 Correct 86 ms 13712 KB Output is correct
13 Correct 97 ms 13796 KB Output is correct
14 Correct 93 ms 13664 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 11 ms 4152 KB Output is correct
3 Correct 71 ms 11624 KB Output is correct
4 Correct 95 ms 13904 KB Output is correct
5 Incorrect 91 ms 13728 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 9 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 -