oj.uz

Submission #1032918

# Submission time Handle Problem Language Result Execution time Memory
1032918 2024-07-24T10:49:53 Z parsadox2 Highway Tolls (IOI18_highway) C++17
51 / 100
 228 ms 13552 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;
	}
	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:140:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  140 |  answer(s , t);
      |  ~~~~~~^~~~~~~
highway.cpp:140: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 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 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 12 ms 3416 KB Output is correct
3 Correct 182 ms 9196 KB Output is correct
4 Correct 176 ms 9580 KB Output is correct
5 Correct 119 ms 9396 KB Output is correct
6 Correct 176 ms 9304 KB Output is correct
7 Correct 146 ms 9156 KB Output is correct
8 Correct 112 ms 9404 KB Output is correct
9 Correct 159 ms 9276 KB Output is correct
10 Correct 136 ms 9720 KB Output is correct
11 Correct 197 ms 10084 KB Output is correct
12 Correct 148 ms 10108 KB Output is correct
13 Correct 162 ms 10072 KB Output is correct
14 Correct 156 ms 10648 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3672 KB Output is correct
2 Correct 25 ms 4728 KB Output is correct
3 Correct 30 ms 6356 KB Output is correct
4 Correct 92 ms 12572 KB Output is correct
5 Correct 96 ms 11444 KB Output is correct
6 Correct 104 ms 13168 KB Output is correct
7 Correct 108 ms 13552 KB Output is correct
8 Correct 96 ms 12408 KB Output is correct
9 Correct 95 ms 13116 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 13 ms 3416 KB Output is correct
3 Correct 132 ms 8036 KB Output is correct
4 Correct 135 ms 9528 KB Output is correct
5 Correct 132 ms 9568 KB Output is correct
6 Correct 166 ms 9448 KB Output is correct
7 Correct 138 ms 9516 KB Output is correct
8 Correct 177 ms 9560 KB Output is correct
9 Correct 168 ms 9204 KB Output is correct
10 Correct 134 ms 9384 KB Output is correct
11 Correct 204 ms 9780 KB Output is correct
12 Correct 201 ms 10868 KB Output is correct
13 Correct 178 ms 10196 KB Output is correct
14 Correct 177 ms 10500 KB Output is correct
15 Correct 105 ms 9400 KB Output is correct
16 Correct 100 ms 9392 KB Output is correct
17 Correct 213 ms 10360 KB Output is correct
18 Correct 183 ms 10612 KB Output is correct
19 Correct 136 ms 9480 KB Output is correct
20 Correct 175 ms 11372 KB Output is correct
21 Correct 133 ms 9580 KB Output is correct
22 Correct 114 ms 9428 KB Output is correct
23 Correct 122 ms 9720 KB Output is correct
24 Correct 138 ms 9980 KB Output is correct
25 Correct 228 ms 12688 KB Output is correct

Subtask #5
0 / 18.0

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