Submission #61657

#	Time	Username	Problem	Language	Result	Execution time	Memory
61657		gs13105	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	290 ms	42448 KiB

minmaxtree

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

vector<int> arr[70010];
int par[70010][18];
int dep[70010];

void f(int x, int p)
{
    par[x][0] = p;
    for(int i = 1; i < 18; i++)
        par[x][i] = par[par[x][i - 1]][i - 1];

    for(int y : arr[x])
    {
        if(y == p)
            continue;

        dep[y] = dep[x] + 1;
        f(y, x);
    }
}

int lca(int x, int y)
{
    if(dep[y] > dep[x])
        swap(x, y);

    int t = dep[x] - dep[y];
    for(int i = 0; i < 18; i++)
        if(t & (1 << i))
            x = par[x][i];

    if(x == y)
        return x;

    for(int i = 17; i >= 0; i--)
    {
        if(par[x][i] != par[y][i])
        {
            x = par[x][i];
            y = par[y][i];
        }
    }
    assert(x != y);
    assert(par[x][0] == par[y][0]);
    return par[x][0];
}

struct uf
{
    int upar[70010];

    int root(int x)
    {
        return x == upar[x] ? x : (upar[x] = root(upar[x]));
    }

    bool merge(int x, int y)
    {
        assert(x != 1 && y != 1);
        x = root(x);
        y = root(y);
        if(x == y)
            return 0;
        if(dep[x] < dep[y])
            upar[y] = x;
        else
            upar[x] = y;
        return 1;
    }
};

struct str
{
    int x, y, z;
    bool operator <(const str &a) const
    {
        return z < a.z;
    }
};

vector<str> m, M;
uf muf, Muf;
int midx[70010];
int Midx[70010];
set<int> mlis[70010];
set<int> Mlis[70010];
int res[70010];

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, k, i, j;
    scanf("%d", &n);
    for(i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        arr[x].push_back(y);
        arr[y].push_back(x);
    }
    scanf("%d", &k);
    for(i = 0; i < k; i++)
    {
        char c;
        int x, y, z;
        scanf(" %c%d%d%d", &c, &x, &y, &z);

        if(c == 'm')
            m.push_back({ x, y, z });
        else
            M.push_back({ x, y, z });
    }

    memset(midx, -1, sizeof midx);
    memset(Midx, -1, sizeof Midx);
    dep[1] = 0;
    f(1, 1);
    for(i = 1; i <= n; i++)
        muf.upar[i] = Muf.upar[i] = i;

    sort(m.rbegin(), m.rend());
    sort(M.begin(), M.end());

    for(i = 0; i < m.size(); i++)
    {
        int r = lca(m[i].x, m[i].y);
        for(j = 0; j < 2; j++)
        {
            int x = (j == 0) ? m[i].x : m[i].y;
            while(dep[x] > dep[r])
            {
                if(midx[x] == -1)
                {
                    mlis[i].insert(x);
                    midx[x] = i;
                }

                while(1)
                {
                    x = muf.root(x);
                    int t = par[x][0];
                    if(midx[t] != -1)
                        muf.merge(x, t);
                    else
                    {
                        x = t;
                        break;
                    }
                }
            }
        }
    }
    for(i = 0; i < M.size(); i++)
    {
        int r = lca(M[i].x, M[i].y);
        for(j = 0; j < 2; j++)
        {
            int x = (j == 0) ? M[i].x : M[i].y;
            while(dep[x] > dep[r])
            {
                if(Midx[x] == -1)
                {
                    Mlis[i].insert(x);
                    Midx[x] = i;
                }

                while(1)
                {
                    x = Muf.root(x);
                    int t = par[x][0];
                    if(Midx[t] != -1)
                        Muf.merge(x, t);
                    else
                    {
                        x = t;
                        break;
                    }
                }
            }
        }
    }

    for(i = 1; i <= n; i++)
        assert(midx[i] == -1 || Midx[i] == -1 || m[midx[i]].z < M[Midx[i]].z);

    set<pair<int, int>> s;
    for(i = 0; i < m.size(); i++)
        s.insert({ (int)mlis[i].size(), i });
    for(i = 0; i < M.size(); i++)
        s.insert({ (int)Mlis[i].size(), (int)(i + m.size()) });

    while(!s.empty())
    {
        int x, y;
        tie(x, y) = *s.begin();
        s.erase(s.begin());

        if(y < m.size())
        {
            int t = *mlis[y].begin();
            assert(res[t] == 0);
            res[t] = m[y].z;

            for(int z : mlis[y])
            {
                if(Midx[z] == -1)
                    continue;

                s.erase({ (int)Mlis[Midx[z]].size(), (int)(Midx[z] + m.size()) });
                Mlis[Midx[z]].erase(z);
                s.insert({ (int)Mlis[Midx[z]].size(), (int)(Midx[z] + m.size()) });
            }
        }
        else
        {
            y -= m.size();
            int t = *Mlis[y].begin();
            assert(res[t] == 0);
            res[t] = M[y].z;

            for(int z : Mlis[y])
            {
                if(midx[z] == -1)
                    continue;

                s.erase({ (int)mlis[midx[z]].size(), midx[z] });
                mlis[midx[z]].erase(z);
                s.insert({ (int)mlis[midx[z]].size(), midx[z] });
            }
        }
    }

    for(i = 2; i <= n; i++)
        printf("%d %d %d\n", i, par[i][0], res[i]);
    return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < m.size(); i++)
                ~~^~~~~~~~~~
minmaxtree.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < M.size(); i++)
                ~~^~~~~~~~~~
minmaxtree.cpp:207:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < m.size(); i++)
                ~~^~~~~~~~~~
minmaxtree.cpp:209:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < M.size(); i++)
                ~~^~~~~~~~~~
minmaxtree.cpp:218:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(y < m.size())
            ~~^~~~~~~~~~
minmaxtree.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:117: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:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:126:14: 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, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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