oj.uz

Submission #60969

# Submission time Handle Problem Language Result Execution time Memory
60969 2018-07-25T04:39:53 Z spencercompton Min-max tree (BOI18_minmaxtree) C++14
58 / 100
 1000 ms 63828 KB 
#include <bits/stdc++.h>
using namespace std;
class Edge{
public:
	int to, rev;
	bool cap;
	Edge(int a, bool b, int c){
		to = a;
		cap = b;
		rev = c;
	}
};
class Flow{
public:
	int n = 140010;
	vector<int> to[140010];
	vector<int> rev[140010];
	vector<bool> cap[140010];
	int sz[140010];
	int dist[140010];
	int nxt[140010];
	bool v[140010];
	int li[140010];
	int point;
	Flow(){
		for(int i = 0; i<n; i++){
			dist[i] = -1;
		}
	}
	void add(int i, int j){
		to[i].push_back(j);
		to[j].push_back(i);
		cap[i].push_back(true);
		cap[j].push_back(false);
		rev[i].push_back(sz[j]++);
		rev[j].push_back(sz[i]++);
	}
	bool dfs(int now){
		if(now==1){
			return true;
		}
		for(; nxt[now]<sz[now]; nxt[now]++){
			int i = nxt[now];
			if(cap[now][i] && dist[to[now][i]] == dist[now]+1 && dfs(to[now][i])){
				cap[now][i] = false;
				cap[to[now][i]][rev[now][i]] = true;
				return true;
			}
		}
		return false;
	}
	int bfs(){
		dist[0] = 0;
		point = 1;
		v[0] = false;
		nxt[0] = 0;
		for(int i = 0; i<point; i++){
			int now = li[i];
			for(int j = 0; j<sz[now]; j++){
				if(dist[to[now][j]]==-1 && cap[now][j]>0){
					dist[to[now][j]] = dist[now]+1;
					li[point++] = to[now][j];
					nxt[to[now][j]] = 0;
					if(to[now][j]==1){
						return 1;
					}
				}
			}
		}
		return 0;
	}
	int flow(){
		int ans = 0;
		while(bfs()>0){
			//do nothing
			for(int i = 0; i<sz[0]; i++){
				if(dist[to[0][i]]==1 && cap[0][i] && dfs(to[0][i])){
					cap[0][i] = false;
					cap[to[0][i]][rev[0][i]] = true;
				}
			}
			for(int i = 0; i<point; i++){
				dist[li[i]] = -1;
			}
		}
		return ans;
	}
};
int maxi[70000];
int mini[70000];
int lc[18][70000];
vector<int> adj[70000];
set<int> maxs[70000];
set<int> mins[70000];
vector<int> remmax[70000];
vector<int> remmin[70000];
int h[70000];
int dfs1(int now, int from, int x){
	lc[0][now] = from;
	h[now] = x;
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		dfs1(to,now,x+1);
	}
}
int mgmin(int a, int b){
	if(mins[a].size()>mins[b].size()){
		swap(a,b);
	}
	for(auto it = mins[a].begin(); it!=mins[a].end(); it++){
		mins[b].insert(*it);
	}
	mins[a].clear();
	return b;
}
int mgmax(int a, int b){
	if(maxs[a].size()>maxs[b].size()){
		swap(a,b);
	}
	for(auto it = maxs[a].begin(); it!=maxs[a].end(); it++){
		maxs[b].insert(*it);
	}
	maxs[a].clear();
	return b;
}
int lca(int a, int b){
	if(a==b){
		return a;
	}
	if(h[a] < h[b]){
		swap(a,b);
	}
	for(int i = 17; i>=0; i--){
		if(lc[i][a]!=-1 && h[lc[i][a]]>=h[b]){
			a = lc[i][a];
		}
	}
	if(a==b){
		return a;
	}
	for(int i = 17; i>=0; i--){
		int toa = lc[i][a];
		int tob = lc[i][b];
		if(toa!=tob){
			a = toa;
			b = tob;
		}
	}
	return lc[0][a];
}
pair<int, int> go(int now, int from){
	//returns minid, maxid
	pair<int, int> ret = make_pair(now,now);
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(to==from){
			continue;
		}
		pair<int, int> got = go(to,now);
		ret.first = mgmin(ret.first,got.first);
		ret.second = mgmax(ret.second,got.second);
	}
	for(int i = 0; i<remmax[now].size(); i++){
		maxs[ret.second].erase(maxs[ret.second].find(remmax[now][i]));
	}
	for(int i = 0; i<remmin[now].size(); i++){
		mins[ret.first].erase(mins[ret.first].find(remmin[now][i]));
	}
	if(maxs[ret.second].size()>0){
		maxi[now] = *maxs[ret.second].begin();
	}
	else{
		maxi[now] = -1;
	}
	if(mins[ret.first].size()>0){
		mini[now] = *mins[ret.first].rbegin();
	}
	else{
		mini[now] = -1;
	}
	return ret;
}
int main(){
	// cout << "MAIN " << endl;
	// Flow f = Flow();
	// cout << "X " << endl;
	// f.add(0,1);
	// f.add(0,4);
	// f.add(0,69);
	// f.add(69,42);
	// f.add(42,13);
	// f.add(42,1);
	// cout << "Y " << endl;
	// cout << f.flow() << endl;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i<n; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs1(0,-1,0);
	for(int i = 1; i<18; i++){
		for(int j = 0; j<n; j++){
			if(lc[i-1][j]==-1){
				lc[i][j] = -1;
			}
			else{
				lc[i][j] = lc[i-1][lc[i-1][j]];
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i<q; i++){
		string s;
		int a, b, v;
		cin >> s >> a >> b >> v;
		a--;
		b--;
		int l = lca(a,b);
		if(s=="M"){
			//maxi
			maxs[a].insert(v);
			maxs[b].insert(v);
			remmax[l].push_back(v);
		}
		else{
			mins[a].insert(v);
			mins[b].insert(v);
			remmin[l].push_back(v);
		}
	}
	go(0,-1);
	map<int, int> m;
	map<int, int> rev;
	int point = 2+n;
	Flow f = Flow();
	for(int i = 1; i<n; i++){
		if(mini[i]!=-1 && m.find(mini[i])==m.end()){
			rev[point] = mini[i];
			f.add(point,1);
			m[mini[i]] = point++;
		}
		if(maxi[i]!=-1 && m.find(maxi[i])==m.end()){
			rev[point] = maxi[i];
			f.add(point,1);
			m[maxi[i]] = point++;
		}
	}
	for(int i = 1; i<n; i++){
		f.add(0,2+i);
		if(mini[i]!=-1){
			f.add(2+i,m[mini[i]]);
		}
		if(maxi[i]!=-1){
			f.add(2+i,m[maxi[i]]);
		}
	}
	f.flow();
	for(int i = 1; i<n; i++){
		int found = -1;
		for(int j = 0; j<f.sz[2+i]; j++){
			int to = f.to[2+i][j];
			if(to!=0 && f.cap[2+i][j]==0){
				found = rev[to];
			}
		}
		
		if(found!=-1){
			cout << (i+1) << " " << (lc[0][i]+1) << " " << found << "\n";
		}
		else if(maxi[i]!=-1){
			cout << (i+1) << " " << (lc[0][i]+1) << " " << maxi[i] << "\n";
		}
		else if(mini[i]!=-1){
			cout << (i+1) << " " << (lc[0][i]+1) << " " << mini[i] << "\n";
		}
		else{
			cout << (i+1) << " " << (lc[0][i]+1) << " " << 69 << "\n";
		}
	}
}

Compilation message

minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
minmaxtree.cpp: In function 'std::pair<int, int> go(int, int)':
minmaxtree.cpp:157:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:166:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmax[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmin[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24568 KB Output is correct
2 Correct 25 ms 24680 KB Output is correct
3 Correct 29 ms 24696 KB Output is correct
4 Correct 24 ms 24704 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 62280 KB Output is correct
2 Correct 825 ms 62280 KB Output is correct
3 Correct 814 ms 62280 KB Output is correct
4 Correct 814 ms 63828 KB Output is correct
5 Correct 954 ms 63828 KB Output is correct
6 Correct 826 ms 63828 KB Output is correct
7 Correct 761 ms 63828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 63828 KB Output is correct
2 Correct 475 ms 63828 KB Output is correct
3 Correct 408 ms 63828 KB Output is correct
4 Correct 478 ms 63828 KB Output is correct
5 Correct 512 ms 63828 KB Output is correct
6 Correct 641 ms 63828 KB Output is correct
7 Correct 479 ms 63828 KB Output is correct
8 Correct 487 ms 63828 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24568 KB Output is correct
2 Correct 25 ms 24680 KB Output is correct
3 Correct 29 ms 24696 KB Output is correct
4 Correct 24 ms 24704 KB Output is correct
5 Correct 946 ms 62280 KB Output is correct
6 Correct 825 ms 62280 KB Output is correct
7 Correct 814 ms 62280 KB Output is correct
8 Correct 814 ms 63828 KB Output is correct
9 Correct 954 ms 63828 KB Output is correct
10 Correct 826 ms 63828 KB Output is correct
11 Correct 761 ms 63828 KB Output is correct
12 Correct 411 ms 63828 KB Output is correct
13 Correct 475 ms 63828 KB Output is correct
14 Correct 408 ms 63828 KB Output is correct
15 Correct 478 ms 63828 KB Output is correct
16 Correct 512 ms 63828 KB Output is correct
17 Correct 641 ms 63828 KB Output is correct
18 Correct 479 ms 63828 KB Output is correct
19 Correct 487 ms 63828 KB Output is correct
20 Correct 962 ms 63828 KB Output is correct
21 Correct 786 ms 63828 KB Output is correct
22 Correct 953 ms 63828 KB Output is correct
23 Correct 872 ms 63828 KB Output is correct
24 Execution timed out 1043 ms 63828 KB Time limit exceeded
25 Halted 0 ms 0 KB -