제출 #170450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170450		Retro3014	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	234 ms	25192 KiB

minmaxtree

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 70000;
const int MAX_K = 20;

int N, K;
string str;
vector<int> gp[MAX_N+1];
int p[MAX_N+1], up[MAX_N+1][MAX_K+1], lv[MAX_N+1];
bool vst[MAX_N+1];
struct Query{
	int idx, x, y;
	int d;
	bool operator <(const Query &a)const{
		return d<a.d;
	}
};
vector<Query> qmx, qmn;

int lca(int x, int y){
	for(int i=MAX_K-1; i>=0; i--){
		if(lv[up[x][i]]>=lv[y])	x = up[x][i];
		if(lv[up[y][i]]>=lv[x])	y = up[y][i];
	}
	if(x==y)	return x;
	for(int i=MAX_K-1; i>=0; i--){
		if(up[x][i]!=up[y][i]){
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

void dfs(int x){
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	vst[x] = true;
	for(int i : gp[x]){
		if(!vst[i]){
			p[i] = x; lv[i] = lv[x]+1;
			dfs(i);
		}
	}
}
int mx[MAX_N+1], mn[MAX_N+1];

int g[MAX_N+1];
void ig(){
	for(int i=1; i<=N; i++)	g[i] = i;
}
int fg(int x){
	return (x==g[x])?x:g[x] = fg(g[x]);
}
void ug(int x, int y){
	x = fg(x); y = fg(y);
	g[y] = x;
}

bool chk2[MAX_N+1];
bool chk[MAX_N+1];
vector<int> cost;
vector<pii> gp2[MAX_N+1];
set<int> st;
struct S{
	int a, b, c;
};
vector<S> ans;
vector<int> vt;
int use[MAX_N+1];
int deg[MAX_N+1];

int main(){
	scanf("%d", &N);
	for(int i=1; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	}
	lv[1] = 1; dfs(1);
	scanf("%d", &K);
	for(int i=0; i<K; i++){
		cin>>str;
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		if(str[0]=='M'){
			qmx.pb({i, a, b, c});
		}else{
			qmn.pb({i, a, b, -c});
		}
		cost.pb(c);
		st.insert(i);
	}
	sort(qmx.begin(), qmx.end()); sort(qmn.begin(), qmn.end());
	ig();
	for(int i=2; i<=N; i++)	mx[i] = mn[i] = -1;
	for(int i=0; i<qmx.size(); i++){
		Query q = qmx[i];
		int l = lca(q.x, q.y);
		int nxt;
		while(1){
			q.x = fg(q.x);
			if(lv[p[q.x]]>=lv[l]){
				mx[q.x] = q.idx;
			}else{
				break;
			}
			ug(l, q.x);
			q.x = p[q.x];
		}
		while(1){
			q.y = fg(q.y);
			if(lv[p[q.y]]>=lv[l]){
				mx[q.y] = q.idx;
			}else{
				break;
			}
			ug(l, q.y);
			q.y = p[q.y];
		}
	}
	ig();
	for(int i=0; i<qmn.size(); i++){
		Query q = qmn[i];
		int l = lca(q.x, q.y);
		int nxt;
		while(1){
			q.x = fg(q.x);
			if(lv[p[q.x]]>=lv[l]){
				mn[q.x] = q.idx;
			}else{
				break;
			}
			ug(l, q.x);
			q.x = p[q.x];
		}
		while(1){
			q.y = fg(q.y);
			if(lv[p[q.y]]>=lv[l]){
				mn[q.y] = q.idx;
			}else{
				break;
			}
			ug(l, q.y);
			q.y = p[q.y];
		}
	}
	for(int i=2; i<=N; i++){
		//cout<<mx[i]<<" "<<mn[i]<<endl;
		if(mx[i]!=-1){
			if(mn[i]!=-1){
				gp2[mx[i]].pb({mn[i], i});
				gp2[mn[i]].pb({mx[i], i});
				deg[mx[i]]++; deg[mn[i]]++;
			}else{
				if(!chk[mx[i]]){
					chk[mx[i]] = true;
					vt.pb(mx[i]);
					chk2[i] = true;
					ans.pb({i, p[i], cost[mx[i]]});
					use[mx[i]] = i;
				}
			}
		}else{
			if(mn[i]!=-1){
				if(!chk[mn[i]]){
					chk[mn[i]] = true;
					vt.pb({mn[i]});
					chk2[i] = true;
					ans.pb({i, p[i], cost[mn[i]]});
					use[mn[i]] = i;
				}
			}
		}
	}
	for(int i=0; i<K; i++){
		if(!chk[i] && gp2[i].size()==1){
			pii pp = gp2[i][0];
			chk[i] = true;
			ans.pb({pp.second, p[pp.second], cost[i]});
			chk2[pp.second] = true;
			vt.pb(i);
			use[i] = pp.second;
			deg[pp.first]--;
		}
	}
	while(!st.empty()){
		int t, k=-1;
		if(vt.empty()){
			cout<<1<<endl;
			t = (*st.begin());
			for(pii i : gp2[t]){
				if(!chk2[i.second]){
					k = i.second;
					deg[i.first]--;
					break;
				}
			}
			chk[t] = true;
			ans.pb({k, p[k], cost[t]});
			chk2[k] = true;
		}else{
			t = vt.back(); vt.pop_back();
		}
		st.erase(t);
		for(pii pr : gp2[t]){
			if(!chk2[pr.second] && !chk[pr.first]){
				chk[pr.first] = true;
				vt.pb(pr.first);
				ans.pb({pr.second, p[pr.second], cost[pr.first]});
				chk2[pr.second] = true;
			}else if(chk2[pr.second] && !chk[pr.first]){
				if(deg[pr.first]==1){
					int tmp;
					for(pii i : gp2[pr.first]){
						if(!chk2[i.second]){
							deg[i.first]--;
							tmp = i.second; break;
						}
					}
					chk[pr.first] = true;
					ans.pb({tmp, p[tmp], cost[pr.first]});
					chk2[tmp] = true;
					vt.pb(pr.first);
				}
			}
		}
	}
	for(int i=2; i<=N; i++){
		if(!chk2[i]){
			if(mn[i]!=-1){
				ans.pb({i, p[i], mn[i]});
			}else{
				ans.pb({i, p[i], mx[i]});
			}
		}
	}
	for(int i=0; i<ans.size(); i++){
		printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<qmx.size(); i++){
               ~^~~~~~~~~~~
minmaxtree.cpp:122:7: warning: unused variable 'nxt' [-Wunused-variable]
   int nxt;
       ^~~
minmaxtree.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<qmn.size(); i++){
               ~^~~~~~~~~~~
minmaxtree.cpp:148:7: warning: unused variable 'nxt' [-Wunused-variable]
   int nxt;
       ^~~
minmaxtree.cpp:260:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++){
               ~^~~~~~~~~~~
minmaxtree.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:100:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &K);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:107:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d%d%d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:244:24: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
      ans.pb({tmp, p[tmp], cost[pr.first]});
                   ~~~~~^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42