oj.uz

답안 #61466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61466 2018-07-26T04:47:47 Z koosaga(#1775) Min-max tree (BOI18_minmaxtree) C++11
36 / 100
 1000 ms 21032 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 70005;

int n, m;
vector<int> gph[MAXN];
map<int, int> mp;
int dep[MAXN], par[17][MAXN];
int emax[MAXN], emin[MAXN], cost[MAXN];
int s[MAXN], e[MAXN];

void dfs(int x, int p){
	for(auto &i : gph[x]){
		if(i != p){
			dep[i] = dep[x] + 1;
			par[0][i] = x;
			dfs(i, x);
		}
	}
}

int lca(int s, int e){
	if(dep[s] > dep[e]) swap(s, e);
	int dx = dep[e] - dep[s];
	for(int i=0; i<17; i++){
		if((dx >> i) & 1) e = par[i][e];
	}
	for(int i=16; i>=0; i--){
		if(par[i][s] != par[i][e]){
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s != e) return par[0][s];
	return s;
}

struct bipartite_matching{
	vector<int> gph[MAXN];
	int l[MAXN], r[MAXN];
	void init(){
		memset(l, -1, sizeof(l));
		memset(r, -1, sizeof(r));
	}
	void add_edge(int s, int e){
		gph[s].push_back(e);
	}
	bool vis[MAXN];
	bool dfs(int x){
		if(vis[x]) return 0;
		vis[x] = 1;
		for(auto &i : gph[x]){
			if(r[i] == -1 || dfs(r[i])){
				r[i] = x;
				l[x] = i;
				return 1;
			}
		}
		return 0;
	}
	void match(int k){
		for(int i=0; i<k; i++){
			if(l[i] == -1){
				memset(vis, 0, sizeof(vis));
				dfs(i);
			}
		}
	}
}bpm;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n-1; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dfs(1, -1);
	for(int i=1; i<17; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	bpm.init();
	memset(emin, -1, sizeof(emin));
	memset(emax, 0x3f, sizeof(emax));
	scanf("%d",&m);
	for(int i=0; i<m; i++){
		char buf[5];
		int s, e, x;
		scanf("%s %d %d %d",buf,&s,&e,&x);
		cost[i] = x;
		mp[x] = i;
		int l = lca(s, e);
		if(*buf == 'M'){
			for(int j=s; j!=l; j=par[0][j]){
				emax[j] = min(emax[j], x);
			}
			for(int j=e; j!=l; j=par[0][j]){
				emax[j] = min(emax[j], x);
			}
		}
		else{
			for(int j=s; j!=l; j=par[0][j]){
				emin[j] = max(emin[j], x);
			}
			for(int j=e; j!=l; j=par[0][j]){
				emin[j] = max(emin[j], x);
			}
		}
	}
	for(int i=2; i<=n; i++){
		int l = -1, r = -1;
		if(mp.find(emin[i]) != mp.end()) l = mp[emin[i]];
		if(mp.find(emax[i]) != mp.end()) r = mp[emax[i]];
		if(~l) bpm.add_edge(l, i-2);
		if(~r) bpm.add_edge(r, i-2);
	}
	bpm.match(m);
	// l : left -> right fun
	// r : right -> left fun
	for(int i=2; i<=n; i++){
		printf("%d %d ", par[0][i], i);
		if(bpm.r[i-2] == -1) printf("%d\n", emin[i]);
		else printf("%d\n", cost[bpm.r[i-2]]);
	}
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
   ~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %d %d %d",buf,&s,&e,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4856 KB Output is correct
2 Correct 7 ms 4964 KB Output is correct
3 Correct 7 ms 4964 KB Output is correct
4 Correct 8 ms 4964 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 886 ms 21032 KB Output is correct
2 Correct 830 ms 21032 KB Output is correct
3 Execution timed out 1049 ms 21032 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 21032 KB Output is correct
2 Correct 354 ms 21032 KB Output is correct
3 Correct 321 ms 21032 KB Output is correct
4 Correct 313 ms 21032 KB Output is correct
5 Correct 409 ms 21032 KB Output is correct
6 Correct 452 ms 21032 KB Output is correct
7 Correct 387 ms 21032 KB Output is correct
8 Correct 411 ms 21032 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4856 KB Output is correct
2 Correct 7 ms 4964 KB Output is correct
3 Correct 7 ms 4964 KB Output is correct
4 Correct 8 ms 4964 KB Output is correct
5 Correct 886 ms 21032 KB Output is correct
6 Correct 830 ms 21032 KB Output is correct
7 Execution timed out 1049 ms 21032 KB Time limit exceeded
8 Halted 0 ms 0 KB -