oj.uz

답안 #60946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60946 2018-07-25T04:05:18 Z spencercompton Min-max tree (BOI18_minmaxtree) C++11
58 / 100
 1000 ms 52864 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 dist[140010];
	int nxt[140010];
	bool v[140010];
	Flow(){

	}
	void add(int i, int j){
		adj[i].push_back(Edge(j,1,adj[j].size()));
		adj[j].push_back(Edge(i,0,adj[i].size()-1));
	}
	int dfs(int now, int f){
		if(now==1){
			return f;
		}
		int did = 0;
		for(; nxt[now]<adj[now].size() && 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;
		}
		vector<int> li;
		dist[0] = 0;
		li.push_back(0);
		v[0] = false;
		nxt[0] = 0;
		for(int i = 0; i<li.size(); i++){
			int now = li[i];
			for(int j = 0; j<adj[now].size(); j++){
				int to = adj[now][j].to;
				if(dist[to]==-1 && adj[now][j].cap>0){
					dist[to] = dist[now]+1;
					li.push_back(to);
					v[to] = false;
					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 member function 'int Flow::dfs(int, int)':
minmaxtree.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; nxt[now]<adj[now].size() && f>0; ){
         ~~~~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::bfs()':
minmaxtree.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<li.size(); i++){
                  ~^~~~~~~~~~
minmaxtree.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j<adj[now].size(); j++){
                   ~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:106: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:155:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:164:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<remmax[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:167: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:269: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 17 ms 15736 KB Output is correct
2 Correct 21 ms 15848 KB Output is correct
3 Correct 21 ms 15884 KB Output is correct
4 Correct 19 ms 15884 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 779 ms 45500 KB Output is correct
2 Correct 607 ms 45500 KB Output is correct
3 Correct 784 ms 45500 KB Output is correct
4 Correct 909 ms 47020 KB Output is correct
5 Correct 729 ms 47020 KB Output is correct
6 Correct 795 ms 47020 KB Output is correct
7 Correct 702 ms 47020 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 47020 KB Output is correct
2 Correct 428 ms 47020 KB Output is correct
3 Correct 353 ms 47020 KB Output is correct
4 Correct 422 ms 47020 KB Output is correct
5 Correct 550 ms 47020 KB Output is correct
6 Correct 527 ms 47020 KB Output is correct
7 Correct 427 ms 47020 KB Output is correct
8 Correct 521 ms 47020 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 21 ms 15848 KB Output is correct
3 Correct 21 ms 15884 KB Output is correct
4 Correct 19 ms 15884 KB Output is correct
5 Correct 779 ms 45500 KB Output is correct
6 Correct 607 ms 45500 KB Output is correct
7 Correct 784 ms 45500 KB Output is correct
8 Correct 909 ms 47020 KB Output is correct
9 Correct 729 ms 47020 KB Output is correct
10 Correct 795 ms 47020 KB Output is correct
11 Correct 702 ms 47020 KB Output is correct
12 Correct 373 ms 47020 KB Output is correct
13 Correct 428 ms 47020 KB Output is correct
14 Correct 353 ms 47020 KB Output is correct
15 Correct 422 ms 47020 KB Output is correct
16 Correct 550 ms 47020 KB Output is correct
17 Correct 527 ms 47020 KB Output is correct
18 Correct 427 ms 47020 KB Output is correct
19 Correct 521 ms 47020 KB Output is correct
20 Correct 883 ms 47020 KB Output is correct
21 Correct 732 ms 47020 KB Output is correct
22 Correct 891 ms 47020 KB Output is correct
23 Correct 858 ms 47020 KB Output is correct
24 Correct 975 ms 51168 KB Output is correct
25 Execution timed out 1006 ms 52864 KB Time limit exceeded
26 Halted 0 ms 0 KB -