제출 #556147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556147		jamezzz	통행료 (IOI18_highway)	C++17	100 / 100	201 ms	13024 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()

#define maxn 90005

int n,m,a,b,dist[maxn][2],pedge[maxn][2],s[maxn];
ll d;
vi ord[2];
vector<ii> AL[maxn];

void find_pair(int _n,vi u,vi v,int _a,int _b){
	n=_n;a=_a;b=_b;
	m=u.size();
	
	for(int i=0;i<m;++i){
		AL[u[i]].pb({v[i],i});
		AL[v[i]].pb({u[i],i});
	}
	
	vi w(m);
	d=ask(w)/a;
	
	vi pos;
	int lo=0,hi=m-1,mid,res;
	while(lo<=hi){
		mid=(lo+hi)>>1;
		vi w(m);
		for(int i=0;i<=mid;++i)w[i]=1;
		if(ask(w)>d*a)res=mid,hi=mid-1;
		else lo=mid+1;
	}
	int f=res;
	vi r={u[f],v[f]};
	
	memset(dist,-1,sizeof dist);
	for(int i=0;i<2;++i){
		queue<int> q;
		dist[r[i]][i]=0;
		q.push(r[i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			ord[i].pb(u);
			for(auto[v,x]:AL[u]){
				if(dist[v][i]!=-1)continue;
				dist[v][i]=dist[u][i]+1;
				pedge[v][i]=x;
				q.push(v);
			}
		}
	}
	for(int i=0;i<n;++i){
		if(dist[i][1]<dist[i][0])s[i]=1;
	}
	vi ans={0,0};
	for(int x=0;x<2;++x){
		vi pos;
		int idk=pedge[4410][0];//test
		int cnt=0;
		for(int i:ord[x]){
			if(i!=r[x]&&s[i]==x){
				pos.pb(pedge[i][x]);
			}
		}
		vi w(m);
		for(int i=0;i<m;++i){
			if(i!=f&&(s[u[i]]==x||s[v[i]]==x))w[i]=1;
		}
		for(int i:pos)w[i]=0;
		int lo=-1,hi=pos.size()-1,mid,res=-1;
		while(lo<=hi){
			int mid=((lo+hi+2)>>1)-1;
			for(int i=mid+1;i<pos.size();++i)w[pos[i]]=1;
			if(ask(w)==d*a)res=mid,hi=mid-1;
			else lo=mid+1;
			for(int i=mid+1;i<pos.size();++i)w[pos[i]]=0;
		}
		if(res==-1)ans[x]=r[x];
		else{
			int e=pos[res];
			ans[x]=(dist[u[e]][x]>dist[v[e]][x])?u[e]:v[e];
		}
	}
	answer(ans[0],ans[1]);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int i=mid+1;i<pos.size();++i)w[pos[i]]=1;
      |                    ~^~~~~~~~~~~
highway.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int i=mid+1;i<pos.size();++i)w[pos[i]]=0;
      |                    ~^~~~~~~~~~~
highway.cpp:65:7: warning: unused variable 'idk' [-Wunused-variable]
   65 |   int idk=pedge[4410][0];//test
      |       ^~~
highway.cpp:66:7: warning: unused variable 'cnt' [-Wunused-variable]
   66 |   int cnt=0;
      |       ^~~
highway.cpp:77:29: warning: unused variable 'mid' [-Wunused-variable]
   77 |   int lo=-1,hi=pos.size()-1,mid,res=-1;
      |                             ^~~
highway.cpp:41:11: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |  vi r={u[f],v[f]};
      |           ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31