oj.uz

Submission #254176

# Submission time Handle Problem Language Result Execution time Memory
254176 2020-07-29T12:55:54 Z shayan_p Min-max tree (BOI18_minmaxtree) C++14
36 / 100
 1000 ms 14072 KB 
// 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 h[maxn], pr[maxn];

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;
    for(int i = 0; i < k; i++){
	char c;
	cin >> c;
	int a, b, x;
	cin >> a >> b >> x;
	if(h[a] < h[b])
	    swap(a, b);
	while(h[a] > h[b]){
	    if(c == 'M')
		MN(a, x, i);
	    else
		MX(a, x, i);
	    a = pr[a];
	}
	while(a != b){
	    if(c == 'M')
		MN(a, x, i);
	    else
		MX(a, x, i);
	    a = pr[a];
	    if(c == 'M')
		MN(b, x, i);
	    else
		MX(b, x, i);
	    b = pr[b];	    
	}	
    }
    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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3840 KB Output is correct
2 Correct 3 ms 3840 KB Output is correct
3 Correct 2 ms 3840 KB Output is correct
4 Correct 3 ms 3840 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12792 KB Output is correct
2 Correct 86 ms 13176 KB Output is correct
3 Execution timed out 1093 ms 9720 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10360 KB Output is correct
2 Correct 59 ms 11768 KB Output is correct
3 Correct 64 ms 13176 KB Output is correct
4 Correct 65 ms 14072 KB Output is correct
5 Correct 65 ms 12152 KB Output is correct
6 Correct 67 ms 12536 KB Output is correct
7 Correct 65 ms 11944 KB Output is correct
8 Correct 65 ms 11896 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3840 KB Output is correct
2 Correct 3 ms 3840 KB Output is correct
3 Correct 2 ms 3840 KB Output is correct
4 Correct 3 ms 3840 KB Output is correct
5 Correct 112 ms 12792 KB Output is correct
6 Correct 86 ms 13176 KB Output is correct
7 Execution timed out 1093 ms 9720 KB Time limit exceeded
8 Halted 0 ms 0 KB -