제출 #60630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60630		SpaimaCarpatilor	Min-max tree (BOI18_minmaxtree)	C++17	29 / 100	230 ms	18256 KiB

minmaxtree

#include<bits/stdc++.h>

using namespace std;

int N, M, ans[70009], lev[70009], t[70009][18], lft[70009], rgt[70009], x[70009], y[70009], a[70009], b[70009], c[70009], ap[70009];
vector < pair < int, int > > v[70009], h[70009];

void dfs (int nod, int tata)
{
    for (int j=1; (1 << j) <= lev[nod]; j++)
        t[nod][j] = t[t[nod][j - 1]][j - 1];
    for (auto it : v[nod])
        if (it.first != tata)
            lev[it.first] = lev[nod] + 1, t[it.first][0] = nod, dfs (it.first, nod);
}

void moveUp (int &x, int k)
{
    for (int i=0; (1 << i) <= k; i++)
        if (k & (1 << i))
            x = t[x][i];
}

int lca (int x, int y)
{
    if (lev[x] > lev[y]) swap (x, y);
    moveUp (y, lev[y] - lev[x]);
    if (x == y) return x;
    int lg = 0;
    while ((2 << lg) <= lev[x])
        lg ++;
    for (int i=lg; i>=0; i--)
        if (t[x][i] != t[y][i] && t[x][i] != 0)
            x = t[x][i], y = t[y][i];
    return t[x][0];
}

int fa[70009], upMost[70009];
int tata (int i)
{
    if (fa[i] == i) return i;
    return fa[i] = tata (fa[i]);
}

void unite (int i, int j)
{
    i = tata (i);
    j = tata (j);
    fa[i] = j;
    if (lev[upMost[j]] > lev[upMost[i]])
        upMost[j] = upMost[i];
}

void paint (int jos, int sus, int culoare, int col[])
{
    jos = upMost[tata (jos)];
    while (lev[jos] > lev[sus])
    {
        col[jos] = culoare;
        unite (jos, t[jos][0]);
        jos = upMost[tata (jos)];
    }
}

void colorNodes (vector < pair < int, int > > ops, int col[])
{
    for (int i=1; i<=N; i++)
        col[i] = 0, fa[i] = i, upMost[i] = i;
    for (auto o : ops)
    {
        int i = o.second, d = lca (a[i], b[i]);
        paint (a[i], d, i, col);
        paint (b[i], d, i, col);
    }
}

void init ()
{
    vector < pair < int, int > > mi, ma;
    scanf ("%d", &N);
    for (int i=1; i<N; i++)
    {
        scanf ("%d %d", &x[i], &y[i]);
        v[x[i]].push_back ({y[i], i});
        v[y[i]].push_back ({x[i], i});
    }
    dfs (1, -1);
    scanf ("%d\n", &M);
    for (int i=1; i<=M; i++)
    {
        char type;
        scanf ("%c %d %d %d\n", &type, &a[i], &b[i], &c[i]);
        if (type == 'm') mi.push_back ({c[i], i});
        else ma.push_back ({c[i], i});
    }
    sort (mi.begin (), mi.end ());
    reverse (mi.begin (), mi.end ());
    sort (ma.begin (), ma.end ());
    colorNodes (mi, lft);
    colorNodes (ma, rgt);
}

void match (int edge, int op)
{
    ans[edge] = c[op];
}

int X, Y, E;
void findSpanningTree (int nod)
{
    ap[nod] = 2;
    for (auto it : h[nod])
        if (ap[it.first] == 0)
            fa[it.first] = it.second, findSpanningTree (it.first);
        else
        if (ap[it.first] == 2 && it.second != fa[nod])
            X = it.first, Y = nod, E = it.second;
}

void finalDfs (int nod)
{
    ap[nod] = 1;
    for (auto it : h[nod])
        if (it.second != E && ap[it.first] == 2)
            match (it.second, it.first), finalDfs (it.first);
}

void reliefStress (int requirement)
{
    for (auto e : h[requirement])
    {
        int other = e.first;
        if (ap[other] == 0)
            ap[other] = 1, match (e.second, other), reliefStress (other);
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

init ();
for (int i=2; i<=N; i++)
    if (lft[i] > 0 && rgt[i] > 0)
    {
        h[lft[i]].push_back ({rgt[i], i});
        h[rgt[i]].push_back ({lft[i], i});
    }
for (int i=2; i<=N; i++)
    if (lft[i] == 0 || rgt[i] == 0)
    {
        if (lft[i] + rgt[i] == 0) continue;
        if (ap[lft[i]] || ap[rgt[i]]) continue;
        if (lft[i] > 0) match (i, lft[i]), ap[lft[i]] = 1, reliefStress (lft[i]);
        else match (i, rgt[i]), ap[rgt[i]] = 1, reliefStress (rgt[i]);
    }
for (int i=1; i<=M; i++)
    if (ap[i] == 0)
    {
        X = Y = -1;
        fa[i] = -1, findSpanningTree (i);
        assert (X != -1);
        match (E, X);
        finalDfs (X);///omitting the edge X, Y which I keep for satisfying X
    }
assert (ap[0] == 0);
for (int i=2; i<=N; i++)
{
    if (ans[i] == 0) ans[i] = 1;
    printf ("%d %d %d\n", t[i][0], i, ans[i]);
}
return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

minmaxtree.cpp: In function 'void init()':
minmaxtree.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
minmaxtree.cpp:83:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &x[i], &y[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:88:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d\n", &M);
     ~~~~~~^~~~~~~~~~~~
minmaxtree.cpp:92:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%c %d %d %d\n", &type, &a[i], &b[i], &c[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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