Submission #254178

#	Time	Username	Problem	Language	Result	Execution time	Memory
254178		shayan_p	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	226 ms	262148 KiB

minmaxtree

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn];

int dsu[maxn], up[maxn];
int h[maxn], pr[maxn];

void restart_dsu(){
    memset(dsu, -1, sizeof dsu);
    iota(up, up + maxn, 0);
}
int fnd(int u){
    return dsu[u] < 0 ? u : dsu[u] = fnd(dsu[u]);
}
void mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return;
    if(dsu[a] > dsu[b])
	swap(a, b);
    dsu[a]+= dsu[b];
    dsu[b] = a;
    if(h[ up[b] ] < h[ up[a] ])
	up[a] = up[b];
}

void prep(int u, int par = 0){
    h[u] = h[par] + 1;
    pr[u] = par;
    for(int y : v[u])
	if(y != par)
	    prep(y, u);
}

int L[maxn], R[maxn], idL[maxn], idR[maxn];

void MN(int id, int x, int id2){
    if(R[id] > x)
	R[id] = x, idR[id] = id2;
}
void MX(int id, int x, int id2){
    if(L[id] < x)
	L[id] = x, idL[id] = id2;
}

int tp[maxn], to[2 * maxn], nxt[2 * maxn], good[2 * maxn], C;

void add(int a, int b, int c){
    nxt[C] = tp[a], tp[a] = C, to[C] = b, good[C] = c, C++;
    nxt[C] = tp[b], tp[b] = C, to[C] = a, good[C] = c ^ 1, C++;
}

int mark[maxn], choose[maxn];

int cyc(int u, int par = -1){
    mark[u] = 1;
    for(int id = tp[u]; id != -1; id = nxt[id]){
	if(id != par){
	    if(mark[ to[id] ] == 1)
		return u;
	    int num = cyc(to[id], id ^ 1);
	    if(num != -1)
		return num;
	}
    }
    return -1;
}
void go(int u, int par = -1){
    mark[u] = 2;
    for(int id = tp[u]; id != -1; id = nxt[id]){
	if(id != par){
	    if(mark[ to[id] ] == 2)
		choose[good[id] >> 1] = good[id] & 1;
	    else if(mark[ to[id] ] != 3)
		choose[good[id] >> 1] = good[id] & 1, go(to[id], id ^ 1);
	}
    }
    mark[u] = 3;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(tp, -1, sizeof tp);
    memset(idL, -1, sizeof idL);
    memset(idR, -1, sizeof idR);
    
    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
	int a, b;
	cin >> a >> b;
	v[a].PB(b);
	v[b].PB(a);	    
    }
    prep(1);
    for(int i = 2; i <= n; i++){
	L[i] = -inf, R[i] = inf;
    }
    int k;
    cin >> k;
    vector< pair<int, pii> > MXS, MNS;    
    for(int i = 0; i < k; i++){
	char c;
	cin >> c;
	int a, b, x;
	cin >> a >> b >> x;
	if(c == 'M')
	    MNS.PB({x, {a, b}});
	else
	    MXS.PB({x, {a, b}});
    }
    sort(MNS.begin(), MNS.end());
    sort(MXS.begin(), MXS.end());
    reverse(MXS.begin(), MXS.end());

    int counter = 0;
    for(auto x : MNS){
	int a = x.S.F, b = x.S.S, X = x.F;
	while(fnd(a) != fnd(b)){
	    a = up[fnd(a)], b = up[fnd(b)];
	    if(h[a] < h[b])
		swap(a, b);
	    MN(a, X, counter);
	    mrg(a, pr[a]);
	}
	counter++;
    }
    restart_dsu();
    for(auto x : MXS){
	int a = x.S.F, b = x.S.S, X = x.F;
	while(fnd(a) != fnd(b)){
	    a = up[fnd(a)], b = up[fnd(b)];
	    if(h[a] < h[b])
		swap(a, b);
	    MX(a, X, counter);
	    mrg(a, pr[a]);
	}
	counter++;
    }
    
    for(int i = 2; i <= n; i++){
	assert(L[i] <= R[i]);
	if(idL[i] == -1)
	    L[i] = R[i];
	if(idR[i] == -1)
	    R[i] = L[i];
	if(idL[i] == -1 && idR[i] != -1)
	    add(idR[i], idR[i], 2 * i + 1);
	if(idL[i] != -1 && idR[i] == -1)
	    add(idL[i], idL[i], 2 * i);
	if(L[i] == R[i]){
	    if(idL[i] != -1 && idR[i] != -1)
		add(idL[i], idL[i], 2 * i), add(idR[i], idR[i], 2 * i + 1);
	}
	else{
	    assert(idL[i] != -1 && idR[i] != -1);
	    add(idL[i], idR[i], 2 * i + 1);
	}
    }

    for(int i = 0; i < k; i++){
	if(mark[i] == 0){
	    int u = cyc(i);
	    assert(u != -1);
	    go(u);
	}
    }
    for(int i = 2; i <= n; i++){
	cout << i << " " << pr[i] << " " << (choose[i] ? R[i] : L[i]) << "\n";
    }
    return 0;
}

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