| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 117102 | 2019-06-14T20:14:14 Z | Bruteforceman | Min-max tree (BOI18_minmaxtree) | C++11 | 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
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 157 ms | 17332 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | 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 | - |