제출 #78906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78906		bogdan10bos	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	218 ms	89396 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;
typedef pair<pii, int> p3i;

const int NMAX = 70005;

p3i chn[NMAX];
int N, E, K;
int h[NMAX], f[NMAX], eul[NMAX], lg2[2 * NMAX], rmq[18][2 * NMAX];
int st[NMAX], dr[NMAX], c[NMAX], up[NMAX];
vector<int> chnmn, chnmx, edg[NMAX];

void DFS(int nod, int fth)
{
    f[nod] = fth;
    h[nod] = h[fth] + 1;
    rmq[0][++E] = nod;
    eul[nod] = E;
    for(auto nxt: edg[nod])
        if(nxt != fth)
        {
            DFS(nxt, nod);
            rmq[0][++E] = nod;
        }
}

int minh(int a, int b) { return (h[a] < h[b] ? a : b); }
int LCA(int a, int b)
{
    int pa = eul[a], pb = eul[b];
    if(pa > pb) swap(pa, pb);
    int lg = lg2[pb - pa + 1];
    return minh(rmq[lg][pa], rmq[lg][pb - (1 << lg) + 1]);
}

int Up(int x) { if(up[x] == x) return x; return up[x] = Up(up[x]); }

void color(int x, int y, int val)
{
    x = Up(x); y = Up(y);
    while(x != y)
    {
        c[x] = val;
        up[x] = Up(f[x]);
        x = Up(x);
    }
}

namespace Matching
{
    int N, F;
    int node[2 * NMAX];
    int mtc[2 * NMAX], f[2 * NMAX];
    vector<int> edg[2 * NMAX];

    void setN(int _N) { N = _N; }

    void addEdge(int x, int y)
    {
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    int match(int x)
    {
        if(f[x] == F)   return 0;
        f[x] = F;

        for(auto nxt: edg[x])
            if(!mtc[nxt])
            {
                mtc[nxt] = x;
                mtc[x] = nxt;
                return 1;
            }
        for(auto nxt: edg[x])
            if( match(mtc[nxt]) )
            {
                mtc[nxt] = x;
                mtc[x] = nxt;
                return 1;
            }

        return 0;
    }

    void randomize()
    {
        mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
        for(int i = 1; i <= N; i++)
            shuffle(edg[i].begin(), edg[i].end(), gen);
        for(int i = 1; i <= N; i++) node[i] = i;
        shuffle(node + 1, node + N + 1, gen);
    }

    void solve()
    {
        randomize();
        bool newm = true;
        F = 0;
        while(newm)
        {
            F++;
            newm = false;
            for(int i = 1; i <= N; i++)
                if(!mtc[ node[i] ])
                    if( match(node[i]) )
                        newm = true;
        }
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d", &N);
    for(int i = 1; i < N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    DFS(1, 0);
    for(int i = 2; i <= E; i++) lg2[i] = 1 + lg2[i >> 1];
    for(int i = 1; (1 << i) <= E; i++)
        for(int j = 1; j + (1 << i) - 1 <= E; j++)
            rmq[i][j] = minh(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

    scanf("%d\n", &K);
    for(int i = 1; i <= K; i++)
    {
        char ch;
        int x, y, val;
        scanf("%c %d%d%d\n", &ch, &x, &y, &val);
        chn[i] = { {x, y}, val };
        if(ch == 'm')   chnmn.push_back(i);
        else if(ch == 'M')  chnmx.push_back(i);
    }

    sort(chnmn.begin(), chnmn.end(),
         [](int a, int b) { return chn[a].second > chn[b].second; });
    sort(chnmx.begin(), chnmx.end(),
         [](int a, int b) { return chn[a].second < chn[b].second; });

    Matching::setN(N + K);

    for(int i = 1; i <= N; i++) up[i] = i, c[i] = 0;
    for(auto id: chnmn)
    {
        int x = chn[id].first.first, y = chn[id].first.second;
        int val = chn[id].second;
        int lca = LCA(x, y);
        color(x, lca, id);
        color(y, lca, id);
    }
    for(int i = 1; i <= N; i++)
        if(c[i] != 0)
            Matching::addEdge(i, c[i] + N);

    for(int i = 1; i <= N; i++) up[i] = i, c[i] = 0;
    for(auto id: chnmx)
    {
        int x = chn[id].first.first, y = chn[id].first.second;
        int val = chn[id].second;
        int lca = LCA(x, y);
        color(x, lca, id);
        color(y, lca, id);
    }
    for(int i = 1; i <= N; i++)
        if(c[i] != 0)
            Matching::addEdge(i, c[i] + N);

    Matching::solve();

    for(int i = 2; i <= N; i++)
    {
        if(Matching::mtc[i] != 0)
        {
            int ch = Matching::mtc[i] - N;
            printf("%d %d %d\n", f[i], i, chn[ch].second);
        }
        else
        {
            int val = 42;
            if(!Matching::edg[i].empty())   val = chn[ Matching::edg[i][0] - N ].second;
            printf("%d %d %d\n", f[i], i, val);
        }
    }


    return 0;
}

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:162:13: warning: unused variable 'val' [-Wunused-variable]
         int val = chn[id].second;
             ^~~
minmaxtree.cpp:175:13: warning: unused variable 'val' [-Wunused-variable]
         int val = chn[id].second;
             ^~~
minmaxtree.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &K);
     ~~~~~^~~~~~~~~~~~
minmaxtree.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c %d%d%d\n", &ch, &x, &y, &val);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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