oj.uz

답안 #61460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61460 2018-07-26T04:40:34 Z koosaga(#1775) Min-max tree (BOI18_minmaxtree) C++11
0 / 100
 726 ms 21592 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++){
		scanf("%d %d",&s[i],&e[i]);
		gph[s[i]].push_back(e[i]);
		gph[e[i]].push_back(s[i]);
	}
	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=0; i<n-1; i++){
		printf("%d %d ", s[i], e[i]);
		if(bpm.r[i] == -1) printf("%d\n", emin[i]);
		else printf("%d\n", cost[bpm.r[i]]);
	}
}

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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s[i],&e[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:91: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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 726 ms 21592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 287 ms 21592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -