oj.uz

Submission #140279

# Submission time Handle Problem Language Result Execution time Memory
140279 2019-08-02T12:49:11 Z bazsi700 Highway Tolls (IOI18_highway) C++14
0 / 100
 1500 ms 3108 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define hashA 1257958787
#define hashB 1539500609
#define endl "\n"

vector<vector<pair<int,int> > > graph (91000,vector<pair<int,int> >());
bool excluded[91000];
bool inset[91000];
bool was[91000];
bool hasspec[91000];
int siz[91000];
int par[91000];
int n,spec,dist;

void dfs(int v) {
	was[v] = true;
	siz[v] = 1;
	for(auto ed : graph[v]) {
		if(!was[ed.first]) {
			par[ed.first] = v;
			dfs(ed.first);
			if(hasspec[ed.first]) {
				hasspec[v] = true;
			}
			siz[v]+= siz[ed.first];
		}
	}
	if(spec == v) {
		hasspec[v] = true;
	}
}

void putinset(int v) {
	was[v] = inset[v] = true;
	for(auto ed : graph[v]) {
		if(!was[ed.first]) {
			putinset(ed.first);
		}
	}
}

int findset() {
	memset(was,false,sizeof(was));
	memset(inset,false,sizeof(inset));
	int sta;
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		if(!excluded[i]) {
			sta = i;
			cnt++;
		}
	}
	par[sta] = -1;
	dfs(sta);
	int big = sta;
	while(big != -1) {
		sta = big;
		for(auto ed : graph[sta]) {
			if(siz[ed.first] > cnt/2) {
				big = ed.first;
				if(!hasspec[ed.first]) {
					hasspec[ed.first] = true;
				} else {
					hasspec[sta] = false;
				}
				siz[sta] = cnt-siz[ed.first];
				siz[ed.first] = cnt;
				break;
			}
		}
	}
	vector<pair<int,int> > nodes;
	for(auto ed : graph[sta]) {
		nodes.push_back({siz[ed.first],ed.first});
	}
	sort(nodes.begin(),nodes.end());
	int currsiz = 1;
	inset[sta] = true;
	was[sta] = true;
	memset(was,false,sizeof(was));
	bool isspec = false;
	for(auto el : nodes) {
		if(abs(cnt/2-currsiz+el.first) <= abs(cnt/2-currsiz)) {
			currsiz+= el.first;
			putinset(el.second);
			if(hasspec[el.second]) {
				isspec = true;
			}
		} else {
			break;
		}
	}
	if(isspec) {
		int cn = 0;
		for(int i = 1; i <= n; i++) {
			if(!excluded[i]) {
				inset[i] = !inset[i];
				if(inset[i]) {
					cn++;
				}
			}
		}
		if(cnt-cn > 1) {
			inset[sta] = true;
		}
	}
	vector<int> toask(n-1,0);
	for(int i = 1; i <= n; i++) {
		if(inset[i] && i != spec) {
			for(auto ed : graph[i]) {
				toask[ed.second] = 1;
			}
		}
	}
	int x = ask(toask);
	if(x > dist) {
		for(int i = 1; i <= n; i++) {
			if(!inset[i] && !excluded[i]) {
				excluded[i] = true;
				cnt--;
			}
		}
		spec = sta;
	} else {
		for(int i = 1; i <= n; i++) {
			if(inset[i]) {
				excluded[i] = true;
				cnt--;
			}
		}
		cnt++;
		inset[sta] = true;
	}
	return cnt;
}

void find_pair(int N, vector<int> u, vector<int> v, int A, int B) {
	n = N;
	for(int i = 0; i < n-1; i++) {
		graph[u[i]].push_back({v[i],i});
		graph[v[i]].push_back({u[i],i});
	}
	vector<int> toask(n-1,0);
	dist = ask(toask);
	spec = -1;
	while(findset() > 1) {}
	answer(spec,spec);
}

Compilation message

highway.cpp: In function 'int findset()':
highway.cpp:63:5: warning: 'sta' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(sta);
  ~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3001 ms 2612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3076 ms 2736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3030 ms 3108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 2680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2936 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2936 KB Incorrect
2 Halted 0 ms 0 KB -