oj.uz

답안 #60958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60958 2018-07-25T04:22:58 Z spencercompton Min-max tree (BOI18_minmaxtree) C++14
58 / 100
 1000 ms 51484 KB 
#include <bits/stdc++.h>
using namespace std;
class Edge{
public:
	int to, cap, rev;
	Edge(int a, int b, int c){
		to = a;
		cap = b;
		rev = c;
	}
};
class Flow{
public:
	int n = 140010;
	vector<Edge> adj[140010];
	int sz[140010];
	int dist[140010];
	int nxt[140010];
	bool v[140010];
	int li[140010];
	Flow(){
 
	}
	void add(int i, int j){

		adj[i].push_back(Edge(j,1,sz[j]++));
		adj[j].push_back(Edge(i,0,sz[i]++));
	}
	int dfs(int now, int f){
		if(now==1){
			return f;
		}
		int did = 0;
		for(; nxt[now]<sz[now] && f>0; ){
			int i = nxt[now];
			int to = adj[now][i].to;
			if(adj[now][i].cap>0 && dist[to] == dist[now]+1){
				int ret = dfs(to,min(f,adj[now][i].cap));
				if(ret>0){
					adj[now][i].cap -= ret;
					adj[to][adj[now][i].rev].cap += ret;
					did += ret;
					f -= ret;
				}
			}
			if(f>0){
				nxt[now]++;
			}
			else{
				break;
			}
		}
		return did;
	}
	int bfs(){
		for(int i = 0; i<n; i++){
			dist[i] = -1;
		}
		dist[0] = 0;
		int 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++){
				int to = adj[now][j].to;
				if(dist[to]==-1 && adj[now][j].cap>0){
					dist[to] = dist[now]+1;
					li[point++] = to;
					nxt[to] = 0;
					if(to==1){
						return 1;
					}
				}
			}
		}
		return 0;
	}
	int flow(){
		int ans = 0;
		while(bfs()>0){
			//do nothing
			ans += dfs(0,n);
		}
		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.adj[2+i].size(); j++){
			int to = f.adj[2+i][j].to;
			if(to!=0 && f.adj[2+i][j].cap==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:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:107: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:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:165:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmax[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:168:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmin[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:270:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<f.adj[2+i].size(); j++){
                  ~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15736 KB Output is correct
2 Correct 19 ms 15844 KB Output is correct
3 Correct 20 ms 15988 KB Output is correct
4 Correct 19 ms 15988 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 825 ms 46204 KB Output is correct
2 Correct 570 ms 46204 KB Output is correct
3 Correct 649 ms 46204 KB Output is correct
4 Correct 684 ms 47600 KB Output is correct
5 Correct 684 ms 47600 KB Output is correct
6 Correct 715 ms 47600 KB Output is correct
7 Correct 738 ms 47600 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 412 ms 47600 KB Output is correct
2 Correct 461 ms 47600 KB Output is correct
3 Correct 435 ms 47600 KB Output is correct
4 Correct 363 ms 47600 KB Output is correct
5 Correct 452 ms 47600 KB Output is correct
6 Correct 578 ms 47600 KB Output is correct
7 Correct 488 ms 47600 KB Output is correct
8 Correct 476 ms 47600 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 15736 KB Output is correct
2 Correct 19 ms 15844 KB Output is correct
3 Correct 20 ms 15988 KB Output is correct
4 Correct 19 ms 15988 KB Output is correct
5 Correct 825 ms 46204 KB Output is correct
6 Correct 570 ms 46204 KB Output is correct
7 Correct 649 ms 46204 KB Output is correct
8 Correct 684 ms 47600 KB Output is correct
9 Correct 684 ms 47600 KB Output is correct
10 Correct 715 ms 47600 KB Output is correct
11 Correct 738 ms 47600 KB Output is correct
12 Correct 412 ms 47600 KB Output is correct
13 Correct 461 ms 47600 KB Output is correct
14 Correct 435 ms 47600 KB Output is correct
15 Correct 363 ms 47600 KB Output is correct
16 Correct 452 ms 47600 KB Output is correct
17 Correct 578 ms 47600 KB Output is correct
18 Correct 488 ms 47600 KB Output is correct
19 Correct 476 ms 47600 KB Output is correct
20 Correct 863 ms 47600 KB Output is correct
21 Correct 762 ms 47600 KB Output is correct
22 Correct 786 ms 47600 KB Output is correct
23 Correct 862 ms 47600 KB Output is correct
24 Execution timed out 1027 ms 51484 KB Time limit exceeded
25 Halted 0 ms 0 KB -