oj.uz

Submission #301595

# Submission time Handle Problem Language Result Execution time Memory
301595 2020-09-18T05:10:19 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;
		cerr<<askv.size()<<endl;
	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 2740 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 3 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 2688 KB Output is correct
10 Correct 3 ms 2720 KB Output is correct
11 Correct 3 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 3072 KB Output is correct
2 Correct 54 ms 5080 KB Output is correct
3 Correct 1456 ms 23552 KB Output is correct
4 Correct 1478 ms 23620 KB Output is correct
5 Correct 1446 ms 23516 KB Output is correct
6 Execution timed out 1520 ms 23564 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5856 KB Output is correct
2 Correct 76 ms 8784 KB Output is correct
3 Correct 80 ms 8892 KB Output is correct
4 Correct 372 ms 27356 KB Output is correct
5 Correct 459 ms 27672 KB Output is correct
6 Correct 311 ms 29744 KB Output is correct
7 Correct 278 ms 21028 KB Output is correct
8 Correct 319 ms 28396 KB Output is correct
9 Correct 255 ms 23296 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2920 KB Output is correct
2 Correct 36 ms 4984 KB Output is correct
3 Correct 296 ms 16888 KB Output is correct
4 Correct 424 ms 21104 KB Output is correct
5 Correct 429 ms 20892 KB Output is correct
6 Correct 421 ms 21088 KB Output is correct
7 Correct 368 ms 20740 KB Output is correct
8 Correct 428 ms 20892 KB Output is correct
9 Correct 761 ms 23372 KB Output is correct
10 Correct 787 ms 22644 KB Output is correct
11 Correct 699 ms 23384 KB Output is correct
12 Correct 946 ms 26240 KB Output is correct
13 Correct 1054 ms 24320 KB Output is correct
14 Correct 811 ms 23548 KB Output is correct
15 Correct 378 ms 20928 KB Output is correct
16 Correct 398 ms 20648 KB Output is correct
17 Correct 1022 ms 25160 KB Output is correct
18 Correct 478 ms 22068 KB Output is correct
19 Correct 385 ms 20612 KB Output is correct
20 Correct 533 ms 21968 KB Output is correct
21 Correct 1136 ms 23732 KB Output is correct
22 Correct 1175 ms 23832 KB Output is correct
23 Correct 830 ms 23796 KB Output is correct
24 Correct 891 ms 24636 KB Output is correct
25 Correct 608 ms 30380 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 311 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 288 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -