Submission #154963

#	Time	Username	Problem	Language	Result	Execution time	Memory
154963		karma	Mergers (JOI19_mergers)	C++14	100 / 100	1524 ms	74412 KiB

mergers

#include<bits/stdc++.h>
#define Task     "test"
#define ll       long long
#define pb       emplace_back
#define mp       make_pair
#define fi       first
#define se       second

using namespace std;

const int N = int(5e5) + 5;
typedef pair<int, int> pii;

vector<int> a[N], g;
int sz[N], n, k, u, v, nstate, full, res = 0;
int cnt[N], s[N], orgcnt[N], deg[N];
int in[N], out[N], Time, Big[N];
bool big[N], choose[N];
vector<pii> vertex;

void DFS(int u, int par) {
    sz[u] = 1; in[u] = ++Time;
    for(int i = 0; i < int(a[u].size()); ++i) {
       if(a[u][i] == par) swap(a[u][i], a[u].back());
       if(a[u][i] != par) {
           DFS(a[u][i], u), sz[u] += sz[a[u][i]];
           if(sz[a[u][i]] > sz[Big[u]]) Big[u] = a[u][i];
       }
    }
    if(u != 1) a[u].pop_back();
    out[u] = Time;
}

void Add(int u, int val) {
    if(cnt[s[u]] == 0) ++nstate;
    if(cnt[s[u]] == orgcnt[s[u]]) --full;
    cnt[s[u]] += val;
    if(cnt[s[u]] == orgcnt[s[u]]) ++full;
    if(cnt[s[u]] == 0) --nstate;
    for(int v: a[u])
        if(!big[v]) Add(v, val);
}

void DSU(int u, bool keep) {
    for(int v: a[u])
        if(v != Big[u]) DSU(v, 0);
    if(Big[u]) DSU(Big[u], 1), big[Big[u]] = 1;
    Add(u, 1);
    if(full == nstate) vertex.pb(mp(in[u], u));
    if(Big[u]) big[Big[u]] = 0;
    if(!keep) Add(u, -1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> k;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v;
        a[u].pb(v), a[v].pb(u);
    }
    for(int i = 1; i <= n; ++i) cin >> s[i], ++orgcnt[s[i]];
    DFS(1, 1); DSU(1, 1);
    sort(vertex.begin(), vertex.end());
    if(vertex.size() == 1) return cout << 0, 0;
    res = vertex.size();
    for(pii p: vertex) {
      while(!g.empty() && out[g.back()] < p.fi) g.pop_back();
      if(g.size()) {
        if(++deg[g.back()] == 1) --res;
      }
      g.pb(p.se);
    }
    if(deg[1] == 1) ++res;
    cout << (res + 1) / 2;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mergers.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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