oj.uz

답안 #139139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139139 2019-07-31T09:57:56 Z random0029 통행료 (IOI18_highway) C++14
18 / 100
 345 ms 18704 KB 
// ItnoE
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = N * 2;
int n, m, ts, X, Y, H[N], Mark[N], V[MXN], U[MXN];
ll ndist, dist;
vector < int > Q, Adj[N];
inline void BFS(int root)
{
	memset(H, -1, sizeof(H));
	H[root] = 0;
	queue < int > qu;
	qu.push(root);
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		for (int id : Adj[v])
		{
			int u = V[id] ^ U[id] ^ v;
			if (H[u] == -1)
				H[u] = H[v] + 1, qu.push(u);
		}
	}
}
inline int GetHeight()
{
	int Mxh = 0;
	for (int i = 0; i < n; i ++)
		Mxh = max(Mxh, H[i]);
	int le = 1, ri = Mxh + 1, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = 0; i < n; i ++)
			if (H[i] >= md)
				for (int id : Adj[i])
				{
					int u = V[id] ^ U[id] ^ i;
					if (H[u] < H[i])
						Q[id] = 1;
				}
		ll dd = ask(Q);
		if (dd == dist)
			ri = md;
		else
			le = md;
	}
	return (le);
}
inline int FindS(int h)
{
	ts ++;
	vector < int > vec;
	for (int i = 0; i < n; i ++)
		if (H[i] == h && (ts == 1 || Mark[i] == 1))
			vec.push_back(i);
	int le = 0, ri = (int)vec.size(), md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = le; i < md; i ++)
			for (int id : Adj[vec[i]])
			{
				int u = V[id] ^ U[id] ^ vec[i];
				if (H[u] < H[vec[i]])
					Q[id] = 1;
			}
		ll dd = ask(Q);
		if (dd == dist)
			le = md;
		else
			ri = md;
	}
	return (vec[le]);
}
void find_pair(int _n, vector < int > _V, vector < int > _U, int _X, int _Y)
{
	n = _n;
	m = (int)_V.size();
	X = _X; Y = _Y;
	for (int i = 0; i < m; i ++)
	{
		V[i] = _V[i]; U[i] = _U[i];
		Adj[V[i]].push_back(i);
		Adj[U[i]].push_back(i);
	}
	Q = vector < int > (m, 0);
	dist = ask(Q);
	ndist = dist / X;
	int le = 0, ri = n, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				Q[id] = 1;
		ll dd = ask(Q);
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				Q[id] = 0;
		if (dist == dd)
			le = md;
		else
		{
			for (int i = le; i < md; i ++)
				for (int id : Adj[i])
					Q[id] = 0;
			ri = md;
		}
	}
	int root = le;
	{
		for (int id : Adj[root])
			Q[id] = 1;
		ll dd = ask(Q);
		if (dd == dist)
			assert(0);
	}
	BFS(root);
	int hs = GetHeight();
	int ht = ndist - hs;
	for (int i = 0; i < n; i ++)
		if (H[i] == ht)
			Mark[i] = 1;
	int s = FindS(hs);
	BFS(s);
	int t = FindS(ndist);
	answer(s, t);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3156 KB Output is correct
3 Correct 4 ms 3072 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 4 ms 3068 KB Output is correct
7 Correct 5 ms 3076 KB Output is correct
8 Correct 4 ms 2984 KB Output is correct
9 Correct 4 ms 3064 KB Output is correct
10 Correct 4 ms 3068 KB Output is correct
11 Correct 4 ms 3064 KB Output is correct
12 Correct 5 ms 3064 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3244 KB Output is correct
2 Correct 33 ms 3668 KB Output is correct
3 Correct 224 ms 8592 KB Output is correct
4 Correct 239 ms 8576 KB Output is correct
5 Correct 233 ms 8576 KB Output is correct
6 Correct 236 ms 8512 KB Output is correct
7 Correct 236 ms 8528 KB Output is correct
8 Correct 252 ms 8604 KB Output is correct
9 Correct 243 ms 8636 KB Output is correct
10 Correct 235 ms 8656 KB Output is correct
11 Correct 322 ms 8384 KB Output is correct
12 Correct 310 ms 8460 KB Output is correct
13 Correct 345 ms 8372 KB Output is correct
14 Correct 256 ms 8372 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3660 KB Output is correct
2 Correct 44 ms 4248 KB Output is correct
3 Correct 38 ms 4832 KB Output is correct
4 Correct 135 ms 8372 KB Output is correct
5 Correct 193 ms 8368 KB Output is correct
6 Correct 131 ms 8364 KB Output is correct
7 Correct 188 ms 8484 KB Output is correct
8 Correct 201 ms 8360 KB Output is correct
9 Correct 169 ms 8384 KB Output is correct

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3128 KB Output is correct
2 Correct 27 ms 3624 KB Output is correct
3 Correct 178 ms 7336 KB Output is correct
4 Correct 234 ms 8852 KB Output is correct
5 Correct 244 ms 8612 KB Output is correct
6 Correct 268 ms 8628 KB Output is correct
7 Correct 238 ms 8516 KB Output is correct
8 Correct 269 ms 8496 KB Output is correct
9 Correct 209 ms 8940 KB Output is correct
10 Correct 243 ms 8584 KB Output is correct
11 Correct 271 ms 8440 KB Output is correct
12 Correct 274 ms 8372 KB Output is correct
13 Correct 334 ms 8388 KB Output is correct
14 Correct 317 ms 8368 KB Output is correct
15 Correct 273 ms 8524 KB Output is correct
16 Correct 290 ms 8644 KB Output is correct
17 Correct 320 ms 8356 KB Output is correct
18 Correct 345 ms 8376 KB Output is correct
19 Correct 200 ms 8520 KB Output is correct
20 Correct 328 ms 8376 KB Output is correct
21 Correct 234 ms 10064 KB Output is correct
22 Correct 175 ms 9488 KB Output is correct
23 Incorrect 270 ms 9508 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 3708 KB Output is correct
2 Correct 32 ms 3792 KB Output is correct
3 Correct 294 ms 8944 KB Output is correct
4 Correct 304 ms 9512 KB Output is correct
5 Runtime error 254 ms 18704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 3692 KB Output is correct
2 Correct 20 ms 3740 KB Output is correct
3 Correct 256 ms 9076 KB Output is correct
4 Correct 267 ms 9400 KB Output is correct
5 Correct 278 ms 9308 KB Output is correct
6 Runtime error 200 ms 18684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -