oj.uz

Submission #1032912

# Submission time Handle Problem Language Result Execution time Memory
1032912 2024-07-24T10:45:02 Z parsadox2 Highway Tolls (IOI18_highway) C++17
5 / 100
 61 ms 5972 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 584 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 600 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 1180 KB Output is correct
3 Runtime error 61 ms 5972 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1620 KB Output is correct
2 Runtime error 12 ms 2648 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 12 ms 1624 KB Output is correct
3 Runtime error 35 ms 4820 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1368 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1112 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -