제출 #407084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407084		Antekb	통행료 (IOI18_highway)	C++14	51 / 100	232 ms	9340 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int d[N];
vector<int> E[N], U, V;
int n, a, b, m;
int dist;
void bfs(int s){
	for(int i=0; i<n; i++){
		d[i]=0;
	}
	vector<int> V;
	d[s]=1;
	V.push_back(s);
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		for(int u:E[v]){
			if(!d[u]){
				d[u]=d[v]+1;
				V.push_back(u);
			}
		}
	}
	/*for(int i=0; i<n; i++){
		cout<<d[i]<<" ";
	}
	cout<<"\n";*/
}
int ile_wys_max(int D){
	vector<int> w(m);
	for(int i=0; i<m; i++){
		if(max(d[U[i]], d[V[i]])<=D)w[i]=1;
	}
	ll k=ask(w);
	if(D==0)dist=k/a;
	//cout<<D<<" "<<dist<<" "<<(k-dist*a)/(b-a)<<"\n";
	return (k-dist*1ll*a)/(b-a);
}
int ile_wys_dokl(int D, int j){
	vector<int> w(m);
	for(int i=0; i<m; i++){
		if(max(d[U[i]], d[V[i]])==D && i<=j)w[i]=1;
	}
	ll k=ask(w);
	//cout<<D<<" "<<j<<" "<<(k-dist*a)/(b-a)<<"\n";
	return (k-dist*1ll*a)/(b-a);
}
void find_pair(int nn, std::vector<int> U2, std::vector<int> V2, int A, int B) {
  	n=nn;
 	a=A;
  	b=B;
  	U=U2;
  	V=V2;
 	m = U.size();
 	if(m!=n-1){
 		answer(1, 3);
 		return;
 	}
 	for(int i=0; i<m; i++){
  		E[U[i]].push_back(V[i]);
  		E[V[i]].push_back(U[i]);
  	}
  	bfs(0);
  	ile_wys_max(0);
  	int l=0, r=n;
  	while(l<r){
  		int m=(l+r)>>1;
  		if(ile_wys_max(m)==dist)r=m;
  		else l=m+1;
  	}
  	//cout<<l<<"\n";
  	int dep=l;
  	l=0, r=n;
  	while(l<r){
  		int m=(l+r)>>1;
  		if(ile_wys_dokl(dep, m)==0)l=m+1;
  		else r=m;
  	}
  	//cout<<l<<"\n";
  	int s=U[l];
  	if(d[s]!=dep)s=V[l];
  	//cout<<s<<"\n";
  	bfs(s);
  	l=0, r=n;
  	while(l<r){
  		int m=(l+r)>>1;
  		if(ile_wys_dokl(dist+1, m)==0)l=m+1;
  		else r=m;
  	}
  	int t=U[l];
  	if(d[t]!=dist+1)t=V[l];
  	//cout<<t<<"\n";
  	answer(s, t);
}

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

highway.cpp: In function 'void bfs(int)':
highway.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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