oj.uz

Submission #117102

# Submission time Handle Problem Language Result Execution time Memory
117102 2019-06-14T20:14:14 Z Bruteforceman Min-max tree (BOI18_minmaxtree) C++11
29 / 100
 361 ms 34972 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);
        }
    }
    set <int> ss;
    for(int i = 1; i < n; i++) {
        int val;
        if(ans[i] == -1) val = 0;
        else {
        	val = rev[ans[i]];
        	ss.insert(val);
        }
        printf("%d %d %d\n", l[i], r[i], val);
    }
    assert(ss.size() == qr);
 }

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from minmaxtree.cpp:1:
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:183:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(ss.size() == qr);
            ~~~~~~~~~~^~~~
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 8 ms 7296 KB Output is correct
3 Correct 7 ms 7296 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 330 ms 31288 KB Output is correct
2 Correct 315 ms 22264 KB Output is correct
3 Correct 321 ms 29176 KB Output is correct
4 Correct 346 ms 34972 KB Output is correct
5 Correct 319 ms 25976 KB Output is correct
6 Correct 361 ms 23800 KB Output is correct
7 Correct 344 ms 22364 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 17332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7168 KB Output is correct
2 Correct 8 ms 7296 KB Output is correct
3 Correct 7 ms 7296 KB Output is correct
4 Correct 7 ms 7168 KB Output is correct
5 Correct 330 ms 31288 KB Output is correct
6 Correct 315 ms 22264 KB Output is correct
7 Correct 321 ms 29176 KB Output is correct
8 Correct 346 ms 34972 KB Output is correct
9 Correct 319 ms 25976 KB Output is correct
10 Correct 361 ms 23800 KB Output is correct
11 Correct 344 ms 22364 KB Output is correct
12 Incorrect 157 ms 17332 KB Output isn't correct
13 Halted 0 ms 0 KB -