Submission #1012627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012627		Belphegor	Highway Tolls (IOI18_highway)	C++14	0 / 100	9 ms	3928 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int dist_a[sz+5],dist_b[sz+5];
int FIND(vector<int>w,vector<int>candidates,int root,int edge,ll d){
	memset(visited,0,sizeof(visited));
	for(int i=0; i<w.size(); i++) w[i] = 1;
    w=vector<int>(w.size(),1);
    
    visited[root] = 0;
	queue<int>q; q.push(root);
	vector<pi>v; v.emplace_back(pi(root,edge));
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(visited[nxt]){
				visited[nxt] = 0;
				v.emplace_back(pi(nxt,id));
				q.push(nxt);
			}
		}
	}
	reverse(v.begin(),v.end());
    for(pi p : v) w[p.second]=0;
    d=ask(w);
	int l = 0,r = v.size()-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[v[i].second] = 1;
		if(ask(w) > d) r = M-1;
		else l = M+1;
		for(int i=0; i<=M; i++) w[v[i].second] = 0;
	}
	return v[l].first;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	for(int i=0; i<n; i++){
		tree[i].clear();
		visited[i] = 0;
		dist_a[i] = dist_b[i] = 1e9;
	}
	int m = U.size();
	for(int i=0; i<U.size(); i++){
		int a = U[i],b = V[i];
		tree[a].emplace_back(pi(b,i));
		tree[b].emplace_back(pi(a,i));
	}
	vector<int>w(m,0);
	ll d = ask(w);
	int l = 0,r = m-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[i] = 1;
		if(ask(w)==d) l = M+1;
		else r = M-1;
		for(int i=0; i<=M; i++) w[i] = 0;
	}
	int e = l;
	int a = U[e],b = V[e];
	dist_a[a] = 0; 
	queue<int>q; q.push(a);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_a[nxt] > dist_a[cur] + 1){
				dist_a[nxt] = dist_a[cur] + 1;
				q.push(nxt);
			}
		}
	}
	dist_b[b] = 0; 
	q.push(b);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_b[nxt] > dist_b[cur] + 1){
				dist_b[nxt] = dist_b[cur] + 1;
				q.push(nxt);
			}
		}
	}
	vector<int>c;
	for(int i=0; i<n; i++){
		if(dist_a[i] < dist_b[i]) c.emplace_back(i);
	}
	a = FIND(w,c,a,e,d); c.clear();
	for(int i=0; i<n; i++){
		if(dist_b[i] < dist_a[i]) c.emplace_back(i);
	}
	b = FIND(w,c,b,e,d); c.clear();
	answer(a,b);
}

Compilation message (stderr)

highway.cpp: In function 'int FIND(std::vector<int>, std::vector<int>, int, int, ll)':
highway.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0; i<w.size(); i++) w[i] = 1;
      |               ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0; i<U.size(); i++){
      |               ~^~~~~~~~~
highway.cpp:73:8: warning: unused variable 'id' [-Wunused-variable]
   73 |    int id = p.second;
      |        ^~
highway.cpp:86:8: warning: unused variable 'id' [-Wunused-variable]
   86 |    int id = p.second;
      |        ^~

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