oj.uz

Submission #154958

# Submission time Handle Problem Language Result Execution time Memory
154958 2019-09-25T16:59:59 Z karma Mergers (JOI19_mergers) C++14
0 / 100
 84 ms 18744 KB 
#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;
bool big[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] += 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) {
    int Big = 0;
    for(int v: a[u])
        if(sz[v] > sz[Big]) Big = v;
    for(int v: a[u])
        if(v != Big) DSU(v, 0);
    if(Big) DSU(Big, 1), big[Big] = 1;
    Add(u, 1);
    if(full == nstate) vertex.pb(mp(in[u], u));
    if(Big) big[Big] = 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());
    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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12148 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 14 ms 12152 KB Output is correct
4 Correct 14 ms 12152 KB Output is correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12148 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 14 ms 12152 KB Output is correct
4 Correct 14 ms 12152 KB Output is correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12148 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 14 ms 12152 KB Output is correct
4 Correct 14 ms 12152 KB Output is correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 18744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12148 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 14 ms 12152 KB Output is correct
4 Correct 14 ms 12152 KB Output is correct
5 Incorrect 13 ms 12152 KB Output isn't correct
6 Halted 0 ms 0 KB -