oj.uz

답안 #253709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253709 2020-07-28T14:41:00 Z Lawliet 통행료 (IOI18_highway) C++17
51 / 100
 237 ms 29688 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 90010;

int n, m;
int A, B;

int depth[MAXN];
int ancEdge[MAXN];

lli dist;

vector<int> adj[MAXN];
vector<int> level[MAXN];
vector<int> indEdge[MAXN];

void DFSInit(int cur, int p, int d)
{
	depth[cur] = d;
	level[d].push_back( cur );

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int ind = indEdge[cur][i];

		if( viz == p ) continue;

		ancEdge[viz] = ind;
		DFSInit( viz , cur , d + 1 );
	}
}

vector<int> activeNodes(int L, int R)
{
	vector<int> c( m , 0 );

	for(int p = L ; p <= R ; p++)
	{
		for(int i = 0 ; i < (int)level[p].size() ; i++)
		{
			int cur = level[p][i];
			c[ ancEdge[cur] ] = 1;
		}
	}

	return c;
}

vector<int> activeNodes(int L, int R, int d)
{
	vector<int> c( m , 0 );

	for(int i = L ; i <= R ; i++)
	{
		int cur = level[d][i];
		c[ ancEdge[cur] ] = 1;
	}

	return c;
}

int findMaxDepth()
{
	int l = 0;
  	int r = n - 1;

  	while( l < r )
  	{
  		int m = ( l + r )/2;

  		if( ask( activeNodes( 1 , m ) ) == dist*B ) r = m;
  		else l = m + 1;
  	}

  	return r;
}

int findNode(int depth)
{
	int l = 0;
	int r = (int)level[depth].size() - 1;

	while( l < r )
	{
		int m = ( l + r )/2;

		if( ask( activeNodes( 0 , m , depth ) ) != dist*A ) r = m;
		else l = m + 1;
	}

	return level[depth][r];
}

void find_pair(int N, vector<int> U, vector<int> V, int a, int b) 
{
	A = a; B = b;
	n = N; m = (int)U.size();

	dist = ask( vector<int>( m , 0 ) )/A;

	for(int i = 0 ; i < m ; i++)
	{
		adj[ U[i] ].push_back( V[i] );
		adj[ V[i] ].push_back( U[i] );

		indEdge[ U[i] ].push_back( i );
		indEdge[ V[i] ].push_back( i );
	}

  	DFSInit( 0 , 0 , 0 );

  	int maxDepth = findMaxDepth();
  	int S = findNode( maxDepth );

  	for(int i = 0 ; i < n ; i++)
  		level[i].clear();

  	DFSInit( S , S , 0 );
  	int T = findNode( dist );

  	answer( S , T );
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6656 KB Output is correct
2 Correct 4 ms 6656 KB Output is correct
3 Correct 6 ms 6656 KB Output is correct
4 Correct 4 ms 6732 KB Output is correct
5 Correct 4 ms 6656 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 4 ms 6656 KB Output is correct
8 Correct 4 ms 6656 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 4 ms 6656 KB Output is correct
11 Correct 5 ms 6656 KB Output is correct
12 Correct 4 ms 6656 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 18 ms 7680 KB Output is correct
3 Correct 235 ms 15768 KB Output is correct
4 Correct 221 ms 15652 KB Output is correct
5 Correct 185 ms 15820 KB Output is correct
6 Correct 206 ms 15616 KB Output is correct
7 Correct 198 ms 15988 KB Output is correct
8 Correct 187 ms 16052 KB Output is correct
9 Correct 182 ms 16088 KB Output is correct
10 Correct 200 ms 15704 KB Output is correct
11 Correct 185 ms 16900 KB Output is correct
12 Correct 207 ms 17604 KB Output is correct
13 Correct 194 ms 16848 KB Output is correct
14 Correct 197 ms 17336 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8320 KB Output is correct
2 Correct 26 ms 9976 KB Output is correct
3 Correct 49 ms 11764 KB Output is correct
4 Correct 117 ms 21872 KB Output is correct
5 Correct 119 ms 21956 KB Output is correct
6 Correct 141 ms 21996 KB Output is correct
7 Correct 134 ms 21880 KB Output is correct
8 Correct 133 ms 21976 KB Output is correct
9 Correct 115 ms 21868 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6784 KB Output is correct
2 Correct 21 ms 7672 KB Output is correct
3 Correct 135 ms 13852 KB Output is correct
4 Correct 182 ms 15552 KB Output is correct
5 Correct 194 ms 15608 KB Output is correct
6 Correct 193 ms 15716 KB Output is correct
7 Correct 196 ms 15776 KB Output is correct
8 Correct 216 ms 15768 KB Output is correct
9 Correct 203 ms 15688 KB Output is correct
10 Correct 198 ms 15688 KB Output is correct
11 Correct 195 ms 16816 KB Output is correct
12 Correct 200 ms 17528 KB Output is correct
13 Correct 192 ms 17136 KB Output is correct
14 Correct 193 ms 17552 KB Output is correct
15 Correct 237 ms 15720 KB Output is correct
16 Correct 212 ms 15584 KB Output is correct
17 Correct 211 ms 17284 KB Output is correct
18 Correct 206 ms 17480 KB Output is correct
19 Correct 198 ms 15784 KB Output is correct
20 Correct 210 ms 18032 KB Output is correct
21 Correct 175 ms 16176 KB Output is correct
22 Correct 177 ms 16064 KB Output is correct
23 Correct 185 ms 16132 KB Output is correct
24 Correct 184 ms 16924 KB Output is correct
25 Correct 219 ms 21340 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 29688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 29432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -