Submission #236410

#	Time	Username	Problem	Language	Result	Execution time	Memory
236410		Charis02	Mergers (JOI19_mergers)	C++14	48 / 100	3084 ms	29924 KiB

mergers

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

struct dsu{
    ll par[N];
    ll sz[N];
    ll col[N];

    ll get(ll x)
    {
        return (par[x] == x) ? x : get(par[x]);
    }

    void join(ll x,ll y)
    {
        ll fx=get(x);
        ll fy = get(y);
        if(fx==fy)
            return;
        if(sz[fx]<sz[fy])
            swap(fx,fy);
        sz[fx]+=sz[fy];
        par[fy]=fx;
    }

    ll get_col(ll x)
    {
        return col[get(x)];
    }
};

ll n,k,state[N],answer;
ll ar[N];
vector < ll > graph[N];
ll cnt = 1;
dsu comp;
vector < ll > fin[N];
ll deg[N];

bool check(ll cur,ll par,ll col)
{
    bool res = false;
    if(state[cur] == col)
        res = true;

    rep(i,0,graph[cur].size())
    {
        ll v =graph[cur][i];

        if(v==par)
            continue;

        if(check(v,cur,col))
        {
            comp.join(cur,v);
            res=true;
        }
    }

    return res;
}

void process_paths()
{
    rep(i,1,n+1)
    {
        if(ar[state[i]] != 0)
            continue;

        ar[state[i]] = cnt++;
        check(i,i,state[i]);
    }

    rep(i,1,n+1)
    {
        if(comp.get_col(i) == 0)
            comp.col[comp.get(i)] = cnt++;
        ar[i] = comp.get_col(i);
    }

    rep(i,1,n+1)
    {
        rep(j,0,graph[i].size())
        {
            ll v = graph[i][j];
            if(ar[i] != ar[v])
                deg[ar[i]]++;
        }
    }

    ll leaves = 0;

    rep(i,1,cnt)
    {
        if(deg[i] == 1)
            leaves++;
    }

    answer = (leaves+1)/2;

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    rep(i,0,n-1)
    {
        ll a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    rep(i,1,n+1)
    {
        comp.par[i]=i;
        comp.sz[i]=1;
        cin >> state[i];
    }

    process_paths();

    cout << answer << endl;

    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'bool check(long long int, long long int, long long int)':
mergers.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
mergers.cpp:62:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
mergers.cpp:62:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
mergers.cpp: In function 'void process_paths()':
mergers.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
mergers.cpp:99:13:
         rep(j,0,graph[i].size())
             ~~~~~~~~~~~~~~~~~~~     
mergers.cpp:99:9: note: in expansion of macro 'rep'
         rep(j,0,graph[i].size())
         ^~~

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