Submission #293480

#	Time	Username	Problem	Language	Result	Execution time	Memory
293480		Aldas25	Mergers (JOI19_mergers)	C++14	0 / 100	113 ms	58736 KiB

mergers

//#pragma GCC optimize("O3")

#include <bits/stdc++.h>
//#include <ctime>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 500100, MAXK = 20;
const ll MOD = 1e9+7;
const ll INF = 1e16;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
 	freopen((s+".out").c_str(),"w",stdout);
}

int n, k;
vi adj[MAXN];
int s[MAXN];
vi bel[MAXN];

int deg[MAXN];

int par[MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    par[b] = a;
}

bool was[MAXN];
int wasCnt[MAXN];
set<int> ch[MAXN];

void dfs (int v, int p) {
    was[s[v]] = true;
    wasCnt[s[v]]++;
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs (u, v);
    }
    wasCnt[s[v]]--;
    if (wasCnt[s[v]] == 0) was[s[v]] = false;

    ch[v].insert(s[v]);
    for (int u : adj[v]) {
        if (u == p) continue;
        if ((int)ch[u].size() > (int)ch[v].size())
            swap(ch[v], ch[u]);
        for (int x : ch[u]) ch[v].insert(x);
        ch[u].clear();
    }


          //  cout << " ch of v="<<v << " :   ";

    for (int x : ch[v]) {
           // cout << " " << x;
        if (was[x]) {
            unite(v,p);
        }
    }
    //cout << endl;
    //cout << "  was of v=" << v << " :  ";
    //FOR(i, 1, k) if (was[i]) cout << " " << i;
    //cout << endl;
}

void dfs2 (int v, int p) {
    for (int u : adj[v]) {
        if (u == p) continue;
        dfs2(u, v);
    }
    if (p == -1) return;
    if (!same(v,p)) {
        deg[find(v)]++;
        deg[find(p)]++;
    }
}

int main() {
    setIO();

    cin >> n >> k;
    REP(n-1) {
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    FOR(i, 1, n) cin >> s[i];
    FOR(i,1 , n) bel[s[i]].pb(i);

    FOR(i, 1, n) par[i] = i;
    dfs (1, -1);
    dfs2(1, -1);

    //FOR(i, 1, n) cout <<"   i = " << i << " deg = " << deg[i] << endl;
    //FOR(i, 1, n) cout << "  i = " << i << " par = " << par[i] << endl;

    int leaves = 0;
    FOR(i, 1, n) if (deg[i] == 1) leaves++;
    int ans = (leaves+1)/2;
    cout << ans <<"\n";

	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'void setIO(std::string)':
mergers.cpp:35:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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