답안 #1055493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055493	2024-08-12T20:06:37 Z	Ahmed57	통행료 (IOI18_highway)	C++17	컴파일 오류	0 ms	0 KB

highway

#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());
    int l = 1 , r = n-1 , 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++){
      |                   ~^~~~~~~~~
highway.cpp:55:9: error: redeclaration of 'long long int l'
   55 |     int l = 1 , r = n-1 , ans2 = 0;
      |         ^
highway.cpp:35:9: note: 'long long int l' previously declared here
   35 |     int l = 0 ,r = n-1 , ans = 0;
      |         ^
highway.cpp:55:17: error: redeclaration of 'long long int r'
   55 |     int l = 1 , r = n-1 , ans2 = 0;
      |                 ^
highway.cpp:35:16: note: 'long long int r' previously declared here
   35 |     int l = 0 ,r = n-1 , ans = 0;
      |                ^