제출 #391500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391500		benedict0724	Mergers (JOI19_mergers)	C++17	0 / 100	117 ms	57648 KiB

mergers

#include <bits/stdc++.h>

using namespace std;
vector<int> adj[500002], col[500002], tree[500002];
vector<pair<int, int>> edge;
int anc[500002], co[500002], d[500002], spr[500002][20];
int link[500002], lcacol[500002];
int ans = 0;

int _find(int x)
{
    if(x == link[x]) return x;
    return link[x] = _find(link[x]);
}
void _unite(int x, int y)
{
    x = _find(x);
    y = _find(y);

    link[x] = y;
}

void dep(int x, int p)
{
    for(int i : adj[x])
    {
        if(i == p) continue;
        d[i] = d[x] + 1;
        spr[i][0] = x;
        dep(i, x);
    }
}

void init(int n)
{
    for(int t=1;t<20;t++) for(int i=1;i<=n;i++)
        spr[i][t] = spr[spr[i][t-1]][t-1];
}

int lca(int a, int b)
{
    if(d[a] < d[b]) swap(a, b);
    int dif = d[a] - d[b];
    for(int i=19;i>=0;i--) if((1<<i) & dif) a = spr[a][i];
    if(a == b) return a;

    for(int i=19;i>=0;i--)
    {
        if(spr[a][i] != spr[b][i] && spr[a][i] != 0 && spr[b][i] != 0)
        {
            a = spr[a][i];
            b = spr[b][i];
        }
    }

    return spr[a][0];
}


int dfs(int x, int p)
{
    int ret = lcacol[co[x]];
    for(int i : adj[x])
    {
        if(i == p) continue;

        int tmp = dfs(i, x);
        if(tmp > d[x]) edge.push_back({i, x});
        else _unite(i, x);

        ret = min(ret, tmp);
    }

    return ret;
}

void solve(int x, int p)
{
    int ret = 0;
    for(int i : tree[x])
    {
        if(i == p) continue;
        solve(i, x);
        ret++;
    }

    ans += ret/2;
    if(p == -1 && ret%2 == 1) ans++;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k; cin >> n >> k;
    for(int i=1;i<n;i++)
    {
        int s, e; cin >> s >> e;
        adj[s].push_back(e);
        adj[e].push_back(s);
    }

    for(int i=1;i<=n;i++) link[i] = i;

    d[1] = 1; dep(1, -1); init(n);

    for(int i=1;i<=n;i++)
    {
        int c; cin >> c;
        co[i] = c;
        col[c].push_back(i);
    }

    for(int i=1;i<=k;i++)
    {
        lcacol[i] = col[i][0];
        for(int j = 1; j < col[i].size();j++)
        {
            lcacol[i] = lca(lcacol[i], col[i][j]);
        }
        lcacol[i] = d[lcacol[i]];
    }

    dfs(1, -1);

    for(auto u : edge)
    {
        int s = u.first, e = u.second;

        s = _find(s); e = _find(e);

        tree[s].push_back(e);
        tree[e].push_back(s);
    }

    solve(_find(1), -1);

    cout << ans;
}

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

mergers.cpp: In function 'int main()':
mergers.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j = 1; j < col[i].size();j++)
      |                        ~~^~~~~~~~~~~~~~~

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