Submission #117104

#	Time	Username	Problem	Language	Result	Execution time	Memory
117104		Bruteforceman	Min-max tree (BOI18_minmaxtree)	C++11	100 / 100	420 ms	41376 KiB

minmaxtree

#include "bits/stdc++.h"
using namespace std;

vector <int> g[70010];
int mn[70010];
int mx[70010];
int par[70010];
int dep[70010];
int sub[70010];
int l[70010];
int r[70010];
int al[70010];
int ar[70010];
bool good[70010];
bool vis[70010];
vector <int> aux[70010];
int ans[70010];

vector <int> mnv[70010], mxv[70010];

void dfs(int x, int p) {
    sub[x] = 1;
    par[x] = p;
    for(int e : g[x]) {
        int y = l[e] ^ r[e] ^ x;  
        if(e != p) {
            dep[y] = 1 + dep[x];
            dfs(y, e);
            sub[x] += sub[y];
        }
    } 
}

void putMin(int x, int y, int val) {
	mnv[x].push_back(val);
	mnv[y].push_back(val);
}
void putMax(int x, int y, int val) {
	mxv[x].push_back(val);
	mxv[y].push_back(val);
}

void solver(int x, int p, set <int> &mns, set <int> &mxs) {
	for(auto i : mnv[x]) mns.insert(i);
	for(auto i : mxv[x]) mxs.insert(i);

	for(auto e : g[x]) {
		int y = l[e] ^ r[e] ^ x;
		if(e == p) continue;
		set <int> p, q;
		solver(y, e, p, q);
		if(p.size() > mns.size()) mns.swap(p);
		if(q.size() > mxs.size()) mxs.swap(q);

		for(auto i : p) {
			if(mns.find(i) == mns.end()) {
				mns.insert(i);
			} else mns.erase(i);
		}
		for(auto i : q) {
			if(mxs.find(i) == mxs.end()) {
				mxs.insert(i);
			} else mxs.erase(i);
		}
	}
	if(mns.size() > 0) {
		mn[p] = *mns.begin();
	}
	if(mxs.size() > 0) {
		mx[p] = *mxs.rbegin();
	}
}
 

void normal_assign(int x) {
    vis[x] = true;
    for(int e : aux[x]) {
        int y = al[e] ^ ar[e] ^ x;
        if(!vis[y] && !good[y]) {
            ans[e] = y;
            normal_assign(y);
        }
    }
}

int anc [70010];
int rev [70010];
int col [70010];
bool found;

void cycle(int x, int p) {
    col[x] = 1;
    anc[x] = p;
    for(int e : aux[x]) {
        int y = al[e] ^ ar[e] ^ x;
        if(col[y] == 0) {
            cycle(y, e);
        } else if (e != p && col[y] == 1 && !found) {
            int cur = x;
            while(cur != y) {
                int pe = anc[cur];
                ans[pe] = cur;
                good[cur] = true;
                cur ^= al[pe] ^ ar[pe];
            }
            good[y] = true;
            ans[e] = y;
            found = true;
        }
    }
    col[x] = -1;
} 

int main () {
    int n;
    scanf("%d", &n);
    memset(ans, -1, sizeof ans);
    for(int i = 0; i <= n; i++) {
        mn[i] = INT_MAX;
        mx[i] = INT_MIN;
    }
    for(int i = 1; i < n; i++) {
		scanf("%d %d", &l[i], &r[i]);
        g[l[i]].push_back(i);
        g[r[i]].push_back(i);
    }
    dfs(1, 0);

    map <int, int> t;
    int qr;
    scanf("%d", &qr);
    for(int i = 1; i <= qr; i++) {
    	char c;
    	int x, y, val;
    	scanf(" %c %d %d %d", &c, &x, &y, &val);
        if(c == 'M') {
            putMin(x, y, val);
        } else {
            putMax(x, y, val);
        }
        t[val] = i;
        rev[i] = val;
    }
    set <int> p, q;
    solver(1, 0, p, q);

    for(int i = 1; i < n; i++) {
    	if(mx[i] == INT_MIN && mn[i] == INT_MAX) continue;
        if(mx[i] == INT_MIN) {
            good[t[mn[i]]] = true;
            ans[i] = t[mn[i]];
        } else if (mn[i] == INT_MAX) {
            good[t[mx[i]]] = true;
            ans[i] = t[mx[i]];
        } else {
            al[i] = t[mx[i]];
            ar[i] = t[mn[i]];
            aux[al[i]].push_back(i);
            aux[ar[i]].push_back(i);
        }
    }
    for(int i = 1; i <= qr; i++) {
        if(col[i] == 0) {
            found = false;
            cycle(i, 0);
        }
    }
    for(int i = 1; i <= qr; i++) {
        if(good[i] && !vis[i]) {
            normal_assign(i);
        }
    }
    for(int i = 1; i < n; i++) {
        int val;
        if(ans[i] == -1) val = max(0, mx[i]);
        else {
        	val = rev[ans[i]];
        }
        printf("%d %d %d\n", l[i], r[i], val);
    }
}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qr);
     ~~~~~^~~~~~~~~~~
minmaxtree.cpp:135:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf(" %c %d %d %d", &c, &x, &y, &val);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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