Submission #502203

#	Time	Username	Problem	Language	Result	Execution time	Memory
502203		iliccmarko	Mergers (JOI19_mergers)	C++14	0 / 100	90 ms	57608 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 1e6;
int n, k, timer, tin[N], cnt[N], b[N], c[N], sz[N];
vector<int> g[N], w[N];
vector<int> grupa;
set<int> s;

void dfstime(int u, int pret)
{
    tin[u] = ++timer;
    w[b[u]].pb(timer);
    for(int x : g[u])
    {
        if(x==pret) continue;
        if(u==1) s.clear();
        dfstime(x, u);
        sz[u] += sz[x];
    }
    s.insert(b[u]);
    sz[u]++;
    if(cnt[b[u]]==w[b[u]].end()-lower_bound(all(w[b[u]]), tin[u])) s.erase(b[u]);
    if(!len(s)) c[u] = 1;
}

int dfs(int u, int pret, int stanje)
{
    int cnt = 0;
    for(int x : g[u])
    {
        if(x==pret) continue;
        if(!stanje)
        {
            if(c[x]) cnt += dfs(x, u, 1);
            else cnt += dfs(x, u, 0);
        }
        else
        {
            cnt += dfs(x, u, stanje+1);
        }
    }
    if(u==1) return 0;
    if(!cnt&&c[u]) cnt++;
    if(stanje==1) grupa.pb(cnt);
    //cout<<u<<' '<<pret<<' '<<cnt<<' '<<c[u]<<endl;
    return cnt;
}

int main()
{
    ios
    cin>>n>>k;
    for(int i = 0;i<n-1;i++)
    {
        int a, b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for(int i = 1;i<=n;i++) cin>>b[i], cnt[b[i]]++;
    dfstime(1, -1);
    dfs(1, -1, 0);
    int ans = 0;
    /*cout<<len(grupa)<<endl;
    for(int x : grupa) cout<<x<<' ';
    cout<<endl;*/
    ans += ((int)len(grupa)+1)/2;
    for(int x : grupa) ans += x/2;

    cout<<ans;



    return 0;
}

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