답안 #78906 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78906	2018-10-09T14:29:24 Z	bogdan10bos	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	218 ms	89396 KB

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;
}

Compilation message

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.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5368 KB	Output is correct
2	Correct	6 ms	5376 KB	Output is correct
3	Correct	6 ms	5616 KB	Output is correct
4	Correct	6 ms	5616 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	169 ms	31340 KB	Output is correct
2	Correct	172 ms	31428 KB	Output is correct
3	Correct	146 ms	34228 KB	Output is correct
4	Correct	173 ms	38748 KB	Output is correct
5	Correct	159 ms	38748 KB	Output is correct
6	Correct	181 ms	41240 KB	Output is correct
7	Correct	163 ms	42884 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	42884 KB	Output is correct
2	Correct	125 ms	42884 KB	Output is correct
3	Correct	116 ms	44940 KB	Output is correct
4	Correct	116 ms	47044 KB	Output is correct
5	Correct	141 ms	47228 KB	Output is correct
6	Correct	144 ms	48984 KB	Output is correct
7	Correct	142 ms	49988 KB	Output is correct
8	Correct	128 ms	51340 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5368 KB	Output is correct
2	Correct	6 ms	5376 KB	Output is correct
3	Correct	6 ms	5616 KB	Output is correct
4	Correct	6 ms	5616 KB	Output is correct
5	Correct	169 ms	31340 KB	Output is correct
6	Correct	172 ms	31428 KB	Output is correct
7	Correct	146 ms	34228 KB	Output is correct
8	Correct	173 ms	38748 KB	Output is correct
9	Correct	159 ms	38748 KB	Output is correct
10	Correct	181 ms	41240 KB	Output is correct
11	Correct	163 ms	42884 KB	Output is correct
12	Correct	122 ms	42884 KB	Output is correct
13	Correct	125 ms	42884 KB	Output is correct
14	Correct	116 ms	44940 KB	Output is correct
15	Correct	116 ms	47044 KB	Output is correct
16	Correct	141 ms	47228 KB	Output is correct
17	Correct	144 ms	48984 KB	Output is correct
18	Correct	142 ms	49988 KB	Output is correct
19	Correct	128 ms	51340 KB	Output is correct
20	Correct	191 ms	56504 KB	Output is correct
21	Correct	150 ms	57332 KB	Output is correct
22	Correct	154 ms	59520 KB	Output is correct
23	Correct	180 ms	61680 KB	Output is correct
24	Correct	184 ms	67228 KB	Output is correct
25	Correct	212 ms	70500 KB	Output is correct
26	Correct	189 ms	72276 KB	Output is correct
27	Correct	189 ms	73712 KB	Output is correct
28	Correct	189 ms	74864 KB	Output is correct
29	Correct	184 ms	77260 KB	Output is correct
30	Correct	172 ms	78520 KB	Output is correct
31	Correct	168 ms	80636 KB	Output is correct
32	Correct	218 ms	83636 KB	Output is correct
33	Correct	178 ms	85288 KB	Output is correct
34	Correct	168 ms	87624 KB	Output is correct
35	Correct	171 ms	89396 KB	Output is correct

답안 #78906

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 29.0 / 29.0

Subtask #4 42.0 / 42.0

Subtask #1
7.0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
29.0 / 29.0

Subtask #4
42.0 / 42.0