oj.uz

Submission #1032917

# Submission time Handle Problem Language Result Execution time Memory
1032917 2024-07-24T10:49:16 Z parsadox2 Highway Tolls (IOI18_highway) C++17
12 / 100
 117 ms 10116 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define F first
#define S second

const int N = 1e5;
int n , m , cand , now;
long long dis;
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;
	long long 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;
	long long 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);
		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;
	}*/
	int s = 0;
	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);
		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:141:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |  answer(s , t);
      |  ~~~~~~^~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 8 ms 3416 KB Output is correct
3 Correct 110 ms 9072 KB Output is correct
4 Correct 114 ms 9228 KB Output is correct
5 Correct 84 ms 9380 KB Output is correct
6 Correct 103 ms 9124 KB Output is correct
7 Correct 108 ms 9072 KB Output is correct
8 Correct 87 ms 9504 KB Output is correct
9 Correct 105 ms 9236 KB Output is correct
10 Correct 117 ms 9400 KB Output is correct
11 Correct 111 ms 9748 KB Output is correct
12 Correct 93 ms 10116 KB Output is correct
13 Correct 107 ms 10000 KB Output is correct
14 Correct 105 ms 9748 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3160 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 8 ms 3416 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -