Submission #1032912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032912		parsadox2	Highway Tolls (IOI18_highway)	C++17	5 / 100	61 ms	5972 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define F first
#define S second

const int N = 1e4;
int n , m , dis , cand , now;
vector <int> adj[N];
vector <int> U , V , vec;
vector <int> marked;
bool a[N] , is_cand[N];

bool aparat(vector <int> A , vector <int> B)
{
	for(int i = 0 ; i < n ; i++)
		a[i] = false;
	for(auto u : A)
		a[u] = true;
	for(int i = 0 ; i < m ; i++)
		marked[i] = false;
	for(int i = 0 ; i < m ; i++)  if((a[U[i]] && !a[V[i]]) || (a[V[i]] && !a[U[i]]))
		marked[i] = true;
	int tmp = ask(marked);
	return (tmp != dis);
}

bool Both(vector <int> A)
{
	for(int i = 0 ; i < n ; i++)
		a[i] = false;
	for(auto u : A)
		a[u] = true;
	for(int i = 0 ; i < m ; i++)
		marked[i] = false;
	for(int i = 0 ; i < m ; i++)  if(a[V[i]] && a[U[i]])
		marked[i] = true;
	int tmp = ask(marked);
	return (tmp != dis);
}

void Bad(vector <int> A)
{
	for(auto u : A)  if(is_cand[u])
	{
		is_cand[u] = false;
		cand--;
	}
}

void Dfs(int v , int p = -1)
{
	vec.push_back(v);
	now -= is_cand[v];
	if(now == 0)
		return;
	//cout << v << " : " << now << endl;
	for(auto u : adj[v])  if(u != p && now != 0)
		Dfs(u , v);
}

vector <int> oth(vector <int> A)
{
	vector <int> B;
	for(int i = 0 ; i < n ; i++)
		a[i] = false;
	for(auto u : A)
		a[u] = true;
	for(int i = 0 ; i < n ; i++)  if(!a[i])
		B.push_back(i);
	return B;
}


void find_pair(int nn , vector <int> UU , vector <int> VV , int A , int B)
{
	n = nn;
	m = UU.size();
	U = UU;
	V = VV;
	marked.resize(m);
	dis = ask(marked);
	for(int i = 0 ; i < m ; i++)
	{
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	if(m != n - 1)
	{
		answer(0 , n - 1);
		return;
	}
	cand = n;
	for(int i = 0 ; i < n ; i++)
		is_cand[i] = true;
	while(cand > 1)
	{
		int tmp = cand/2;
		vec.clear();
		now = tmp;
		Dfs(0);
		//break;
		vector <int> vec2 = oth(vec);
		if(aparat(vec , vec2))
			Bad(vec);
		else
		{
			if(Both(vec))
				Bad(vec2);
			else
				Bad(vec);
		}
	}
	int s;
	for(int i = 0 ; i < n ; i++)  if(is_cand[i])
	{
		s = i;
		break;
	}
	//cout << s << endl;
	for(int i = 0 ; i < n ; i++)
		is_cand[i] = true;
	cand = n;
	while(cand > 1)
	{
		int tmp = cand/2;
		vec.clear();
		now = tmp;
		Dfs(s);
		//break;
		vector <int> vec2 = oth(vec);
		if(aparat(vec , vec2))
			Bad(vec);
		else
			Bad(vec2);
	}
	int t;
	for(int i = 0 ; i < n ; i++)  if(is_cand[i])
		t = i;
	answer(s , t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:142:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |  answer(s , t);
      |  ~~~~~~^~~~~~~
highway.cpp:142:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]

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