Submission #1091707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091707		raphaelp	Mergers (JOI19_mergers)	C++14	100 / 100	708 ms	99120 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int par, vector<vector<int>> &AR, vector<int> &depth, vector<int> &p, int prof)
{
    depth[x] = prof;
    p[x] = par;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == par)
            continue;
        dfs(AR[x][i], x, AR, depth, p, prof + 1);
    }
}
vector<int> lead;
int find(int x) { return (lead[x] == x) ? x : lead[x] = find(lead[x]); }
void dfs2(int x, int p, vector<vector<int>> &AR, int &leafs)
{
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        dfs2(AR[x][i], x, AR, leafs);
    }
    if (AR[x].size() == 1)
        leafs++;
}
int main()
{
    int N, K;
    cin >> N >> K;
    vector<vector<int>> AR(N);
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        AR[a].push_back(b);
        AR[b].push_back(a);
    }
    vector<vector<int>> groups(K);
    vector<int> Tab(N);
    lead.assign(N, 0);
    for (int i = 0; i < N; i++)
        lead[i] = i;
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        Tab[i]--;
        groups[Tab[i]].push_back(i);
    }
    vector<int> depth(N), p(N), occ(N);
    dfs(0, 0, AR, depth, p, 0);
    for (int i = 0; i < K; i++)
    {
        while (groups[i].size() > 1)
        {
            int a = groups[i].back();
            groups[i].pop_back();
            int b = groups[i].back();
            groups[i].pop_back();
            if (occ[a] || occ[b])
            {
                if (occ[a] == 0)
                    groups[i].push_back(a), occ[a] = 0;
                if (occ[b] == 0)
                    groups[i].push_back(b), occ[b] = 0;
                continue;
            }
            occ[a] = 1, occ[b] = 1;
            while (a != b)
            {
                if (depth[b] > depth[a])
                    swap(a, b);
                int next = find(p[a]);
                occ[next] = 1;
                if (Tab[next] > i)
                {
                    for (auto val : groups[Tab[next]])
                        groups[i].push_back(val);
                    groups[Tab[next]].clear();
                }
                if (AR[next].size() < AR[a].size())
                    swap(AR[next], AR[a]);
                for (auto val : AR[a])
                    AR[next].push_back(val);
                lead[a] = next;
                a = next;
            }
            occ[a] = 0;
            groups[i].push_back(a);
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        for (int j = 0; j < AR[i].size(); j++)
        {
            AR[i][j] = find(AR[i][j]);
            if (AR[i][j] == i)
            {
                swap(AR[i][j], AR[i].back());
                AR[i].pop_back();
                j--;
            }
        }
        sort(AR[i].begin(), AR[i].end());
        for (int j = 1; j < AR[i].size(); j++)
        {
            if (AR[i][j] == AR[i][j - 1])
            {
                swap(AR[i][j], AR[i].back());
                AR.pop_back();
                j--;
            }
        }
    }
    int leafs = 0;
    dfs2(find(0), find(0), AR, leafs);
    if (leafs == 1)
        cout << 0;
    else
        cout << leafs / 2 + leafs % 2;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, int)':
mergers.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int, int, std::vector<std::vector<int> >&, int&)':
mergers.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int j = 0; j < AR[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
mergers.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int j = 1; j < AR[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30