oj.uz

답안 #1119593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1119593 2024-11-27T07:28:00 Z vjudge1 Min-max tree (BOI18_minmaxtree) C++17
0 / 100
 1000 ms 75956 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 500001;

using namespace std;
using namespace __gnu_pbds;

ll n, a, b, c, up[N][22], d[N], m, bg[N], h[N];
map <pair <ll, ll>, ll> ax, an, mx, mn;
map <ll, ll> cx, cn, used;
vector <pair <ll, pair <ll, ll>>> k, mxx, mnn;
vector <ll> g[N];

void dfs (ll v, ll pr){
	up[v][0] = pr;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pr){
			ax[{v, g[v][i]}] = ax[{g[v][i], v}] = an[{g[v][i], v}] = an[{v, g[v][i]}] = -1;
			d[g[v][i]] = d[v] + 1; 
			dfs (g[v][i], v);
		}
	}
}

ll lca (ll a, ll b){
	if (d[a] < d[b]){
		swap (a, b);
	}
	ll c = abs (d[a] - d[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

void cnt (ll v, ll pr){
	for (auto i: g[v]){
		if (i != pr){
			cx[mx[{i, v}]]++;
			cn[mn[{i, v}]]++;
			cnt (i, v);
		}
	}
}

void ans (ll v, ll pr){
	for (auto i: g[v]){
		if (i != pr){
			if (ax[{i, v}] != -1 && used[ax[{i, v}]] == 0){
				if (used[{an[{i, v}]}] == 1 || an[{i, v}] == -1){
					cn[an[{i, v}]]--;
					cx[ax[{i, v}]]--;
					used[ax[{i, v}]] = 1;
					k.pb({i, {v, ax[{i, v}]}});
				}
				else{
					if (cx[ax[{i, v}]] < cn[an[{i, v}]]){
						cn[an[{i, v}]]--;
						cx[ax[{i, v}]]--;
						used[ax[{i, v}]] = 1;
						k.pb({i, {v, ax[{i, v}]}});
					}
					else{
						cn[an[{i, v}]]--;
						cx[ax[{i, v}]]--;
						used[an[{i, v}]] = 1;
						k.pb({i, {v, an[{i, v}]}});
					}
				}
			}
			else{
				if (an[{i, v}] == -1){
					k.pb({i, {v, 0}});
					cx[ax[{i, v}]]--;
				}
				else{
					k.pb({i, {v, an[{i, v}]}});
					used[an[{i, v}]] = 1;
					cx[ax[{i, v}]]--;
					cn[an[{i, v}]]--;
				}
			}
			ans (i, v);
		}
	}
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	d[1] = 1;
	dfs (1, 1);
	cin >> m;
	for (int i = 1; i <= m; i++){
		char ch;
		cin >> ch >> a >> b >> c;
		if (ch == 'M'){
			mxx.pb ({c, {a, b}});
		}
		else{
			mnn.pb ({c, {a, b}});
		}
	}
	sort (all (mxx));
	sort (all (mnn));
	reverse (all (mxx));
	for (auto i: mxx){
		ll lc = lca (i.S.F, i.S.S);
		a = i.S.F, b = i.S.S;
		while (a != lc){
			ax[{a, up[a][0]}] = ax[{up[a][0], a}] = i.F;
			a = up[a][0];
		}
		while (b != lc){
			ax[{b, up[b][0]}] = ax[{up[b][0], b}] = i.F;
			b = up[b][0];
		}
	}
	for (auto i: mnn){
		ll lc = lca (i.S.F, i.S.S);
		a = i.S.F, b = i.S.S;
		while (a != lc){
			an[{a, up[a][0]}] = an[{up[a][0], a}] = i.F;
			a = up[a][0];
		}
		while (b != lc){
			an[{b, up[b][0]}] = an[{up[b][0], b}] = i.F;
			b = up[b][0];
		}
	}
	cnt (1, 1);
	ans (1, 1);
	for (auto i: k){
		cout << i.F << ' ' << i.S.F << ' ' << i.S.S << '\n';
	}
}

Compilation message

minmaxtree.cpp: In function 'void dfs(long long int, long long int)':
minmaxtree.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 990 ms 75956 KB Output is correct
2 Correct 723 ms 66888 KB Output is correct
3 Execution timed out 1051 ms 52164 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 60520 KB Output is correct
2 Correct 420 ms 61140 KB Output is correct
3 Correct 469 ms 66996 KB Output is correct
4 Correct 428 ms 70476 KB Output is correct
5 Correct 458 ms 62908 KB Output is correct
6 Correct 452 ms 64140 KB Output is correct
7 Correct 493 ms 62080 KB Output is correct
8 Incorrect 498 ms 61808 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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