oj.uz

Submission #117096

# Submission time Handle Problem Language Result Execution time Memory
117096 2019-06-14T19:25:05 Z Bruteforceman Min-max tree (BOI18_minmaxtree) C++11
0 / 100
 1000 ms 18552 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];

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 p, int q, int val) {
    while(dep[p] > dep[q]) {
        int tmp = p;
        p = q;
        q = tmp;
    }
    while(dep[p] < dep[q]) {
        int e = par[q];
        mn[e] = min(mn[e], val);
        q ^= l[e] ^ r[e];
    }
    while(p != q) {
        int e1 = par[p];
        int e2 = par[q];
        mn[e1] = min(mn[e1], val);
        mn[e2] = min(mn[e2], val);
        p ^= l[e1] ^ r[e1];
        q ^= l[e2] ^ r[e2];
    }
    return ;
}
void putMax(int p, int q, int val) {
    while(dep[p] > dep[q]) {
        int tmp = p;
        p = q;
        q = tmp;
    }
    while(dep[p] < dep[q]) {
        int e = par[q];
        mx[e] = max(mx[e], val);
        q ^= l[e] ^ r[e];
    }
    while(p != q) {
        int e1 = par[p];
        int e2 = par[q];
        mx[e1] = max(mx[e1], val);
        mx[e2] = max(mx[e2], val);
        p ^= l[e1] ^ r[e1];
        q ^= l[e2] ^ r[e2];
    }
    return ;
}
void normal_assign(int x) {
    vis[x] = true;
    for(int e : aux[x]) {
        int y = al[e] ^ ar[e] ^ x;
        if(!vis[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;
    }
    for(int i = 1; i < n; i++) {
        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);
            // System.out.println(al[i] + " " + ar[i] + " " + 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 = 0;
        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:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:121: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:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qr);
     ~~~~~^~~~~~~~~~~
minmaxtree.cpp:133: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3968 KB Output is correct
2 Correct 6 ms 3968 KB Output is correct
3 Correct 6 ms 3968 KB Output is correct
4 Incorrect 6 ms 3968 KB Output isn't correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 18552 KB Output is correct
2 Correct 219 ms 15992 KB Output is correct
3 Execution timed out 1066 ms 11000 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3968 KB Output is correct
2 Correct 6 ms 3968 KB Output is correct
3 Correct 6 ms 3968 KB Output is correct
4 Incorrect 6 ms 3968 KB Output isn't correct