oj.uz

Submission #210296

# Submission time Handle Problem Language Result Execution time Memory
210296 2020-03-17T02:20:35 Z ToMmyDong Mergers (JOI19_mergers) C++11
0 / 100
 81 ms 33516 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define SZ(i) int(i.size())
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"#%d: %s = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
template<typename It> ostream& _printRng(ostream &os,It bg,It ed)
{
    os<<"{";
    for(It it=bg;it!=ed;it++) {
        os<<(it==bg?"":",")<<*it;
    }
    os<<"}";
    return os;
}
template<typename T> ostream &operator << (ostream &os,vector<T> &v){return _printRng(os,v.begin(), v.end());}
template<typename T> void pary(T bg, T ed){_printRng(cerr,bg,ed);cerr<<endl;}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#define pary(...)
#endif

const int MAXN = 500005;
const ll MOD = 1000000007;

int n, k;
vector<pii> edges;
vector<int> G[MAXN], T[MAXN];

vector<int> tree, comp;

int s[MAXN], cnt[MAXN], cur[MAXN];

set<int> open;
void dfsEdg(int nd, int pa, int id) {
    for (auto eid : G[nd]) {
        int v = edges[eid].X ^ edges[eid].Y ^ nd;
        if (v != pa) {
            dfsEdg(v, nd, eid);
        }
    }

    if (id == -1) {
        return;
    }
    cur[s[nd]]++;
    if (cur[s[nd]] == 1) {
        open.insert(s[nd]);
    }
    if (cur[s[nd]] == cnt[s[nd]]) {
        open.erase(s[nd]);
    }
    if (open.empty()) {
        tree.eb(id);
    } else {
        comp.eb(id);
    }
}

int djs[MAXN];

int fnd (int nd) {
    return nd == djs[nd] ? djs[nd] : djs[nd] = fnd(djs[nd]);
}

void mrg (int x, int y) {
    x = fnd(x);
    y = fnd(y);
    djs[x] = y;
}

int deg[MAXN];
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n >> k;
    REP (i, n-1) {
        int u,v;
        cin >> u >> v;
        edges.eb(u, v);
        G[u].eb(i);
        G[v].eb(i);
    }

    REP1 (i, n) {
        cin >> s[i];
        cnt[s[i]]++;
    }

    dfsEdg(1, 1, -1);

    for (int i=1; i<=n; i++) {
        djs[i] = i;
    }

    for (auto id : comp) {
        mrg(edges[id].X, edges[id].Y);
    }
    vector<int> nodes;
    for (int i=1; i<=n; i++) {
        if (fnd(i) == i) {
            nodes.eb(i);
        }
    }

    debug(tree, comp, nodes);
    for (auto id : tree) {
        int u, v;
        tie(u, v) = edges[id];

        deg[fnd(u)]++;
        deg[fnd(v)]++;
    }

    int ans = 0;
    vector<int> deg_cnt;
    for (auto v : nodes) {
        deg_cnt.eb(deg[v]);
    }
    debug(deg_cnt);

    sort(deg_cnt.rbegin(), deg_cnt.rend());
    while (deg_cnt.size() > 1 && deg_cnt.back() == 1) {
        deg_cnt.pop_back();
    }

    for (auto d : deg_cnt) {
        ans += (d+1)/2;
    }

    cout << ans << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 31472 KB Output is correct
2 Correct 81 ms 33516 KB Output is correct
3 Incorrect 21 ms 24056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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