oj.uz

Submission #154949

# Submission time Handle Problem Language Result Execution time Memory
154949 2019-09-25T16:04:33 Z karma Mergers (JOI19_mergers) C++14
0 / 100
 75 ms 12116 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(2e5) + 5;
typedef pair<int, int> pii;

vector<int> a[N];
int sz[N], n, k, u, v, nstate, full, res = 0;
int cnt[N], s[N], orgcnt[N], f[N];
bool big[N], choose[N];

void DFS(int u, int par) {
    sz[u] = 1;
    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();
}

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) choose[u] = 1;
    if(!keep) Add(u, -1);
}

void _DFS(int u) {
    for(int v: a[u]) {
        _DFS(v);
        f[u] = max(f[u], f[v]);
    }
    if(choose[u] && !f[u]) ++res;
}

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);
    _DFS(1);
    cout << res / 2;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:62: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:63: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 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 10788 KB Output is correct
2 Correct 75 ms 12116 KB Output is correct
3 Incorrect 9 ms 5240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -