Submission #294580

#	Time	Username	Problem	Language	Result	Execution time	Memory
294580		Dovran	Highway Tolls (IOI18_highway)	C++11	0 / 100	48 ms	33144 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
#define N 200009
#define pii pair <int, int>
#define ff first
#define ss second
#define sz size
#define pb push_back
#define ll long long

using namespace std;

ll m, ln;
vector<ll>e[N];
vector<int>asd;
map<ll, ll>c[N];

int tap(vector<int>v){
	int l=0, r=v.sz()-1, in;
	while(l<=r){
		int md=(l+r)/2;
		for(int i=0; i<m; i++)
			asd[i]=0;
		for(int i=md; i<v.size(); i++)
			for(auto j:e[v[i]]) asd[c[v[i]][j]]=1;
		ll x=ask(asd);
		if(x!=ln)
			in=md, l=md+1;
		else r=md-1;
		
	}
	return v[in];
}

void find_pair(int n, std::vector<int>u, std::vector<int>v, int a, int b){
	m=u.size();
	for(int i=0; i<m; i++){
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
		
		c[v[i]][u[i]]=i;
		c[u[i]][v[i]]=i;
		
		
		asd.pb(0);
	}
	ln=ask(asd);
	int l=0, r=m-1;
	ll x, in;
	while(r>=l){
		int md=(l+r)/2;
		for(int i = 0; i < m; i++){
			if(i<=md) asd[i] = 1;
			else asd[i]=0;
		}
		
		x=ask(asd);
		
		if(x==ln) l=md+1;
		else in = md, r=md-1;
	}
//	answer(0, 0);
//	return;
	queue<pii> q;
	q.push({u[in], 1});
	q.push({v[in], 2});
	
	int vis[N];
	vector<int> C, D;
	while(!q.empty()){
		int nd=q.front().ff;
		int tp=q.front().ss;
		q.pop();
		if(vis[nd])
			continue;
		vis[nd]=tp;
		if(tp==1)
			C.pb(nd);
		else
			D.pb(nd);
		
		for(auto i:e[nd])
			if(!vis[i])
				vis[i]=tp, q.push({i, tp});
	}
	answer(tap(C), tap(D));
}

Compilation message (stderr)

highway.cpp: In function 'int tap(std::vector<int>)':
highway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=md; i<v.size(); i++)
      |                 ~^~~~~~~~~
highway.cpp:32:13: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |  return v[in];
      |             ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:14: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  q.push({u[in], 1});
      |              ^

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