oj.uz

Submission #301657

# Submission time Handle Problem Language Result Execution time Memory
301657 2020-09-18T05:45:49 Z dsjong Highway Tolls (IOI18_highway) C++14
44 / 100
 1500 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int A, B, N, M;
long long len;
map<pair<int, int>, int>mp;
vector<int>adj[100005];
bool vis[100005];
int par[100005];
vector<pair<int, int>>bord;
void bfs(int src){
	queue<int>q;
	vis[src]=true;
	q.push(src);
	par[src]=-1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:adj[x]){
			if(vis[y]) continue;
			vis[y]=true;
			q.push(y);
			par[y]=x;
			bord.push_back({mp[{x, y}], y});
		}
	}
}
int tin[100005], tout[100005];
int cnt=0;
vector<pair<int, int>>vin, vout;
void dfs(int x, int p){
	tin[x]=cnt++;
	for(int y:adj[x]){
		if(y==p) continue;
		dfs(y, x);
		vin.push_back({tin[y], y});
		vout.push_back({tout[y], y});
	}
	tout[x]=cnt++;
}
vector<int>query, askv;
bool hasB(){
	for(int i=0;i<M;i++) askv[i]=0;
	for(int x:query) askv[x]=1;
	query.clear();
	return ask(askv) > A*len;
}
void find_pair(int _N, std::vector<int> U, std::vector<int> V, int _A, int _B) {
	A=_A, B=_B, N=_N, M=U.size();
	askv.resize(M);
	for(int i=0;i<M;i++) askv[i]=0;
	len=ask(askv)/A;
	for(int i=0;i<M;i++){
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
		mp[{U[i], V[i]}]=i;
		mp[{V[i], U[i]}]=i;
	}
	bfs(0);
	int L=0, R=M-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			query.push_back(bord[i].first);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	int rt=par[bord[L].second];
	dfs(rt, par[rt]);
	sort(vin.begin(), vin.end());
	sort(vout.begin(), vout.end());
	reverse(vin.begin(), vin.end());
	int pt1, pt2;
	//find largest in
	L=0, R=(int) vin.size()-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			int cur=vin[i].S;
			query.push_back(mp[{cur, par[cur]}]);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	pt1=vin[L].S;
	L=0, R=(int) vin.size()-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			int cur=vout[i].S;
			query.push_back(mp[{cur, par[cur]}]);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	pt2=vout[L].S;
	if(pt1==pt2) answer(pt1, rt);
	else answer(pt1, pt2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2944 KB Output is correct
2 Correct 89 ms 4984 KB Output is correct
3 Correct 1475 ms 23520 KB Output is correct
4 Correct 1495 ms 23568 KB Output is correct
5 Correct 1452 ms 23528 KB Output is correct
6 Execution timed out 1522 ms 23476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5788 KB Output is correct
2 Correct 85 ms 8732 KB Output is correct
3 Correct 78 ms 8896 KB Output is correct
4 Correct 369 ms 27432 KB Output is correct
5 Correct 417 ms 27516 KB Output is correct
6 Correct 262 ms 29740 KB Output is correct
7 Correct 235 ms 21000 KB Output is correct
8 Correct 375 ms 28412 KB Output is correct
9 Correct 270 ms 23072 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2880 KB Output is correct
2 Correct 40 ms 5064 KB Output is correct
3 Correct 281 ms 16848 KB Output is correct
4 Correct 452 ms 20988 KB Output is correct
5 Correct 363 ms 21036 KB Output is correct
6 Correct 350 ms 20968 KB Output is correct
7 Correct 357 ms 20716 KB Output is correct
8 Correct 396 ms 20964 KB Output is correct
9 Correct 771 ms 23364 KB Output is correct
10 Correct 790 ms 22680 KB Output is correct
11 Correct 751 ms 23284 KB Output is correct
12 Correct 960 ms 26240 KB Output is correct
13 Correct 1111 ms 24280 KB Output is correct
14 Correct 852 ms 23584 KB Output is correct
15 Correct 372 ms 20984 KB Output is correct
16 Correct 425 ms 20568 KB Output is correct
17 Correct 944 ms 25036 KB Output is correct
18 Correct 448 ms 22036 KB Output is correct
19 Correct 428 ms 20564 KB Output is correct
20 Correct 517 ms 22156 KB Output is correct
21 Correct 1040 ms 23800 KB Output is correct
22 Correct 1077 ms 23916 KB Output is correct
23 Correct 834 ms 23740 KB Output is correct
24 Correct 860 ms 24684 KB Output is correct
25 Correct 579 ms 30444 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 286 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -