제출 #1060487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060487		jamjanek	통행료 (IOI18_highway)	C++14	0 / 100	10 ms	3424 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
long long dist;
int odl[90010][5];
vector<int>graf[90010];
void bfs(int start, int war){
	queue<int>kolejka;
	odl[start][war] = 1;
	kolejka.push(start);
	while(kolejka.size()){
		auto x = kolejka.front();
		kolejka.pop();
		for(auto j: graf[x])
			if(!odl[j][war]){
				odl[j][war] = odl[x][war]+1;
				kolejka.push(j);
			}
	}
}
bool cmp1(int a, int b){
	return odl[a][0] < odl[b][0];
}
bool cmp2(int a, int b){
	return odl[a][1] < odl[b][1];
}
vector<int>w;
vector<int>u, v;
bool czy[90010];

void ustaw(int n, vector<int>&zbior, int sufix){
	for(int i=0;i<n;i++)czy[i] = 0;
	for(int j=0;j<(int)zbior.size();j++)czy[j] = j>=sufix;
	for(int i=0;i<(int)w.size();i++)
		w[i] = czy[u[i]]|czy[v[i]];
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	u = U, v = V;
	int m = U.size(), i;
	w.resize(m, 0);
	dist = ask(w);
	int pocz = -1, kon = m, srodek;
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		for(i=0;i<m;i++)
			w[i] = (i>=srodek);
		if(dist==ask(w)){
			kon = srodek-1;
		}
		else
			pocz = srodek;
		
	}
	for(i=0;i<m;i++){
		graf[U[i]].push_back(V[i]);
		graf[V[i]].push_back(U[i]);
	}
	//krawedz to jest pocz
	bfs(U[pocz], 0);
	bfs(V[pocz], 1);
	vector<int>zbior1, zbior2;
	for(i=0;i<n;i++)
		if(odl[i][0]<odl[i][1])
			zbior1.push_back(i);
	for(i=0;i<n;i++)
		if(odl[i][0]>odl[i][1])
			zbior2.push_back(i);
	sort(zbior1.begin(), zbior1.end(), cmp1);
	sort(zbior2.begin(), zbior2.end(), cmp2);
	
	pocz = -1, kon = zbior1.size();
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		ustaw(n, zbior1, srodek);
		if(dist==ask(w))
			kon = srodek - 1;
		else
			pocz = srodek;
	}
	int S = zbior1[pocz];

	pocz = -1, kon = zbior2.size();
	while(pocz<kon){
		srodek = (pocz+kon+1)/2;
		ustaw(n, zbior2, srodek);
		if(dist==ask(w))
			kon = srodek - 1;
		else
			pocz = srodek;
	}
	int E = zbior2[pocz];
//	printf("%d %d\n", S, E);
	answer(S, E);
}

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