oj.uz

Submission #117104

# Submission time Handle Problem Language Result Execution time Memory
117104 2019-06-14T20:27:42 Z Bruteforceman Min-max tree (BOI18_minmaxtree) C++11
100 / 100
 420 ms 41376 KB 
#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

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.0 / 7.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 31352 KB Output is correct
2 Correct 279 ms 19704 KB Output is correct
3 Correct 278 ms 29176 KB Output is correct
4 Correct 307 ms 35064 KB Output is correct
5 Correct 262 ms 25848 KB Output is correct
6 Correct 278 ms 21772 KB Output is correct
7 Correct 262 ms 19176 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 16252 KB Output is correct
2 Correct 154 ms 17692 KB Output is correct
3 Correct 162 ms 26104 KB Output is correct
4 Correct 160 ms 30328 KB Output is correct
5 Correct 178 ms 19832 KB Output is correct
6 Correct 194 ms 21084 KB Output is correct
7 Correct 162 ms 17912 KB Output is correct
8 Correct 173 ms 17864 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 7 ms 7168 KB Output is correct
3 Correct 7 ms 7168 KB Output is correct
4 Correct 7 ms 7168 KB Output is correct
5 Correct 284 ms 31352 KB Output is correct
6 Correct 279 ms 19704 KB Output is correct
7 Correct 278 ms 29176 KB Output is correct
8 Correct 307 ms 35064 KB Output is correct
9 Correct 262 ms 25848 KB Output is correct
10 Correct 278 ms 21772 KB Output is correct
11 Correct 262 ms 19176 KB Output is correct
12 Correct 152 ms 16252 KB Output is correct
13 Correct 154 ms 17692 KB Output is correct
14 Correct 162 ms 26104 KB Output is correct
15 Correct 160 ms 30328 KB Output is correct
16 Correct 178 ms 19832 KB Output is correct
17 Correct 194 ms 21084 KB Output is correct
18 Correct 162 ms 17912 KB Output is correct
19 Correct 173 ms 17864 KB Output is correct
20 Correct 352 ms 24236 KB Output is correct
21 Correct 309 ms 24356 KB Output is correct
22 Correct 324 ms 25464 KB Output is correct
23 Correct 304 ms 23800 KB Output is correct
24 Correct 376 ms 35724 KB Output is correct
25 Correct 414 ms 41376 KB Output is correct
26 Correct 350 ms 40340 KB Output is correct
27 Correct 407 ms 34492 KB Output is correct
28 Correct 341 ms 25564 KB Output is correct
29 Correct 354 ms 25776 KB Output is correct
30 Correct 296 ms 24028 KB Output is correct
31 Correct 349 ms 23672 KB Output is correct
32 Correct 420 ms 24608 KB Output is correct
33 Correct 376 ms 23516 KB Output is correct
34 Correct 382 ms 23644 KB Output is correct
35 Correct 337 ms 22584 KB Output is correct