oj.uz

답안 #604836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604836 2022-07-25T10:18:46 Z StrawHatWess 통행료 (IOI18_highway) C++17
51 / 100
 178 ms 73276 KB 
#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef vector<int>vi; 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)

typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi; 
#define eb emplace_back

#define FOR(i,a,b) for(int i=a; i<b; i++)

//--------------------

const int MX=2e5; 

int N,M,A,B;
vpi adj[MX];


vi w; 
ll L; 


vi vec[MX], par(MX); 
void dfs(int u, int p, int l=0){
	par[u]=p; 
	for(auto it: adj[u]){
		int v=it.fi, idx=it.se; 
		if(v!=p){
			vec[l].pb(idx); 
			dfs(v,u,l+1); 
		}
	}
}

int check_level(int lvl){
	w.assign(M,0);
	FOR(i,0,lvl+1) for(int ed: vec[i]) w[ed]=1; 

	ll len=ask(w);
	return (len==L*B);
}

void find_pair(int N, vi U, vi V, int A, int B) {

	::N=N; M=sz(U); ::A=A; ::B=B; 
	FOR(i,0,M){
		int u=U[i], v=V[i]; 
		adj[u].eb(v,i); 
		adj[v].eb(u,i);
	}

	w.assign(M,0);
	L=ask(w)/A; 


	dfs(0,0); 

	//BS to find the level of the endpoint
	int l=0, r=N-1, lvl; 
	while(l<=r){
		int m=(l+r)/2; 
		if(check_level(m)) lvl=m, r=m-1; 
		else l=m+1; 
	}

	

	//BS to find the exact edge
	vi tmp=vec[lvl]; 
	l=0, r=sz(tmp)-1; int idx; 
	while(l<=r){
		int m=(l+r)/2; 

		w.assign(M,0); 
		FOR(i,0,m+1) w[tmp[i]]=1; 

		ll len=ask(w); 
		if(len>L*A) idx=tmp[m], r=m-1; 
		else l=m+1;
	}

	int u=U[idx], v=V[idx]; 
	if(par[v]==u) swap(u,v); 
	int s=u; 


	//empty the vec: important
	FOR(i,0,N) vec[i].clear(); 
	dfs(s,s); 

	tmp=vec[L-1]; 
	l=0, r=sz(tmp)-1, idx; 
	while(l<=r){
		int m=(l+r)/2; 

		w.assign(M,0); 
		FOR(i,0,m+1) w[tmp[i]]=1; 

		ll len=ask(w); 
		if(len>L*A) idx=tmp[m], r=m-1; 
		else l=m+1;
	}

	u=U[idx], v=V[idx]; 
	if(par[v]==u) swap(u,v); 
	int t=u;

	answer(s,t); 
}

/*

6 5 1 2 0 3
0 1
2 1
2 3
2 4
0 5


*/

Compilation message

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:101:23: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |  l=0, r=sz(tmp)-1, idx;
      |                       ^
highway.cpp:91:13: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |  int u=U[idx], v=V[idx];
      |             ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10448 KB Output is correct
2 Correct 20 ms 11080 KB Output is correct
3 Correct 123 ms 16312 KB Output is correct
4 Correct 131 ms 16236 KB Output is correct
5 Correct 170 ms 16344 KB Output is correct
6 Correct 108 ms 16200 KB Output is correct
7 Correct 118 ms 16460 KB Output is correct
8 Correct 115 ms 16552 KB Output is correct
9 Correct 161 ms 16584 KB Output is correct
10 Correct 111 ms 16284 KB Output is correct
11 Correct 175 ms 18012 KB Output is correct
12 Correct 170 ms 19540 KB Output is correct
13 Correct 130 ms 18240 KB Output is correct
14 Correct 120 ms 18640 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 12240 KB Output is correct
2 Correct 29 ms 13956 KB Output is correct
3 Correct 49 ms 15704 KB Output is correct
4 Correct 83 ms 26320 KB Output is correct
5 Correct 131 ms 26324 KB Output is correct
6 Correct 111 ms 26388 KB Output is correct
7 Correct 145 ms 26332 KB Output is correct
8 Correct 99 ms 26328 KB Output is correct
9 Correct 111 ms 26324 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10448 KB Output is correct
2 Correct 21 ms 11068 KB Output is correct
3 Correct 85 ms 15024 KB Output is correct
4 Correct 114 ms 16212 KB Output is correct
5 Correct 111 ms 16228 KB Output is correct
6 Correct 110 ms 16264 KB Output is correct
7 Correct 155 ms 16220 KB Output is correct
8 Correct 116 ms 16180 KB Output is correct
9 Correct 144 ms 16260 KB Output is correct
10 Correct 156 ms 16300 KB Output is correct
11 Correct 170 ms 17920 KB Output is correct
12 Correct 117 ms 19296 KB Output is correct
13 Correct 137 ms 18496 KB Output is correct
14 Correct 167 ms 19184 KB Output is correct
15 Correct 111 ms 16288 KB Output is correct
16 Correct 117 ms 16584 KB Output is correct
17 Correct 158 ms 18752 KB Output is correct
18 Correct 151 ms 18996 KB Output is correct
19 Correct 111 ms 16276 KB Output is correct
20 Correct 131 ms 20076 KB Output is correct
21 Correct 131 ms 16640 KB Output is correct
22 Correct 142 ms 16636 KB Output is correct
23 Correct 135 ms 16764 KB Output is correct
24 Correct 178 ms 17744 KB Output is correct
25 Correct 136 ms 25324 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 73 ms 73152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 73276 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -