Submission #227201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
227201	2020-04-26T13:29:44 Z	MKopchev	Mergers (JOI19_mergers)	C++14	10 / 100	126 ms	17136 KB

mergers

#include <bits/stdc++.h>
using namespace std;

const int nmax=5e5+42;

int n,k;

int colour[nmax],cnt[nmax];

vector<int> adj[nmax];

int wrong=0;

int seen[nmax];

void add(int val)
{
    val=colour[val];

    if(seen[val]==0)wrong++;
    seen[val]++;
    if(seen[val]==cnt[val])wrong--;
}

void sub(int val)
{
    val=colour[val];

    if(seen[val]==cnt[val])wrong++;
    seen[val]--;
    if(seen[val]==0)wrong--;
}

int SZ[nmax];

void dfs_sz(int node,int par)
{
    SZ[node]=1;
    for(auto k:adj[node])
        if(k!=par)
        {
            dfs_sz(k,node);
            SZ[node]+=SZ[k];
        }
}

int can_divide=0;

void dfs_clean(int node,int par)
{
    sub(node);

    for(auto k:adj[node])
        if(k!=par)
        {
            dfs_clean(k,node);
        }
}

void dfs_add(int node,int par)
{
    add(node);

    for(auto k:adj[node])
        if(k!=par)
        {
            dfs_add(k,node);
        }
}

int ROOT;
int dfs(int node,int par)
{
    bool found=0;

    int big=0;

    for(auto k:adj[node])
        if(k!=par&&SZ[big]<SZ[k])big=k;

    for(auto k:adj[node])
        if(k!=par&&big!=k)
        {
            found=dfs(k,node)|found;

            dfs_clean(k,node);
        }
    /*
    cout<<node<<" -> "<<big<<" "<<found<<" "<<wrong<<endl;

    cout<<"seen(should be empty): ";for(int i=1;i<=k;i++)cout<<seen[i]<<" ";cout<<endl;
    */
    if(big)found=found|dfs(big,node);


    for(auto k:adj[node])
        if(k!=par&&big!=k)
            dfs_add(k,node);

    add(node);

    //cout<<node<<" -> "<<big<<" "<<found<<" "<<wrong<<endl;

    //cout<<"seen: ";for(int i=1;i<=k;i++)cout<<seen[i]<<" ";cout<<endl;

    if(wrong==0&&found==0&&node!=ROOT)
    {
        //cout<<"node= "<<node<<endl;
        found=1;
        can_divide++;
    }
    return found;
}
int main()
{
    scanf("%i%i",&n,&k);

    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%i%i",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++)
    {
        scanf("%i",&colour[i]);
        cnt[colour[i]]++;
    }

    ROOT=1;

    for(int i=n;i>=1;i--)
        if(adj[i].size()>=2){ROOT=i;break;}

    dfs_sz(ROOT,0);

    dfs(ROOT,0);

    printf("%i\n",(can_divide+1)/2);

    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
mergers.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~
mergers.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&colour[i]);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12160 KB	Output is correct
3	Correct	11 ms	12160 KB	Output is correct
4	Correct	11 ms	12032 KB	Output is correct
5	Correct	11 ms	12032 KB	Output is correct
6	Correct	11 ms	12032 KB	Output is correct
7	Correct	11 ms	12032 KB	Output is correct
8	Correct	14 ms	12032 KB	Output is correct
9	Correct	12 ms	12032 KB	Output is correct
10	Correct	11 ms	12032 KB	Output is correct
11	Correct	11 ms	12160 KB	Output is correct
12	Correct	12 ms	12160 KB	Output is correct
13	Correct	11 ms	12032 KB	Output is correct
14	Correct	11 ms	12160 KB	Output is correct
15	Correct	11 ms	12160 KB	Output is correct
16	Correct	11 ms	12032 KB	Output is correct
17	Correct	11 ms	12032 KB	Output is correct
18	Correct	11 ms	12032 KB	Output is correct
19	Correct	11 ms	12032 KB	Output is correct
20	Correct	11 ms	12032 KB	Output is correct
21	Correct	11 ms	12032 KB	Output is correct
22	Correct	11 ms	12032 KB	Output is correct
23	Correct	11 ms	12032 KB	Output is correct
24	Correct	11 ms	12032 KB	Output is correct

Subtask #2
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12160 KB	Output is correct
3	Correct	11 ms	12160 KB	Output is correct
4	Correct	11 ms	12032 KB	Output is correct
5	Correct	11 ms	12032 KB	Output is correct
6	Correct	11 ms	12032 KB	Output is correct
7	Correct	11 ms	12032 KB	Output is correct
8	Correct	14 ms	12032 KB	Output is correct
9	Correct	12 ms	12032 KB	Output is correct
10	Correct	11 ms	12032 KB	Output is correct
11	Correct	11 ms	12160 KB	Output is correct
12	Correct	12 ms	12160 KB	Output is correct
13	Correct	11 ms	12032 KB	Output is correct
14	Correct	11 ms	12160 KB	Output is correct
15	Correct	11 ms	12160 KB	Output is correct
16	Correct	11 ms	12032 KB	Output is correct
17	Correct	11 ms	12032 KB	Output is correct
18	Correct	11 ms	12032 KB	Output is correct
19	Correct	11 ms	12032 KB	Output is correct
20	Correct	11 ms	12032 KB	Output is correct
21	Correct	11 ms	12032 KB	Output is correct
22	Correct	11 ms	12032 KB	Output is correct
23	Correct	11 ms	12032 KB	Output is correct
24	Correct	11 ms	12032 KB	Output is correct
25	Correct	11 ms	12160 KB	Output is correct
26	Correct	13 ms	12160 KB	Output is correct
27	Correct	13 ms	12160 KB	Output is correct
28	Correct	16 ms	12288 KB	Output is correct
29	Correct	13 ms	12288 KB	Output is correct
30	Correct	13 ms	12160 KB	Output is correct
31	Correct	11 ms	12032 KB	Output is correct
32	Correct	13 ms	12416 KB	Output is correct
33	Correct	11 ms	12032 KB	Output is correct
34	Correct	12 ms	12288 KB	Output is correct
35	Correct	13 ms	12288 KB	Output is correct
36	Incorrect	13 ms	12288 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12160 KB	Output is correct
3	Correct	11 ms	12160 KB	Output is correct
4	Correct	11 ms	12032 KB	Output is correct
5	Correct	11 ms	12032 KB	Output is correct
6	Correct	11 ms	12032 KB	Output is correct
7	Correct	11 ms	12032 KB	Output is correct
8	Correct	14 ms	12032 KB	Output is correct
9	Correct	12 ms	12032 KB	Output is correct
10	Correct	11 ms	12032 KB	Output is correct
11	Correct	11 ms	12160 KB	Output is correct
12	Correct	12 ms	12160 KB	Output is correct
13	Correct	11 ms	12032 KB	Output is correct
14	Correct	11 ms	12160 KB	Output is correct
15	Correct	11 ms	12160 KB	Output is correct
16	Correct	11 ms	12032 KB	Output is correct
17	Correct	11 ms	12032 KB	Output is correct
18	Correct	11 ms	12032 KB	Output is correct
19	Correct	11 ms	12032 KB	Output is correct
20	Correct	11 ms	12032 KB	Output is correct
21	Correct	11 ms	12032 KB	Output is correct
22	Correct	11 ms	12032 KB	Output is correct
23	Correct	11 ms	12032 KB	Output is correct
24	Correct	11 ms	12032 KB	Output is correct
25	Correct	11 ms	12032 KB	Output is correct
26	Correct	65 ms	16368 KB	Output is correct
27	Correct	114 ms	16120 KB	Output is correct
28	Correct	13 ms	12160 KB	Output is correct
29	Correct	11 ms	12032 KB	Output is correct
30	Correct	11 ms	12032 KB	Output is correct
31	Incorrect	126 ms	16336 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	16368 KB	Output is correct
2	Correct	70 ms	17136 KB	Output is correct
3	Correct	13 ms	12160 KB	Output is correct
4	Correct	13 ms	12160 KB	Output is correct
5	Correct	11 ms	12160 KB	Output is correct
6	Correct	11 ms	12032 KB	Output is correct
7	Correct	13 ms	12288 KB	Output is correct
8	Correct	125 ms	16504 KB	Output is correct
9	Incorrect	13 ms	12160 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12160 KB	Output is correct
3	Correct	11 ms	12160 KB	Output is correct
4	Correct	11 ms	12032 KB	Output is correct
5	Correct	11 ms	12032 KB	Output is correct
6	Correct	11 ms	12032 KB	Output is correct
7	Correct	11 ms	12032 KB	Output is correct
8	Correct	14 ms	12032 KB	Output is correct
9	Correct	12 ms	12032 KB	Output is correct
10	Correct	11 ms	12032 KB	Output is correct
11	Correct	11 ms	12160 KB	Output is correct
12	Correct	12 ms	12160 KB	Output is correct
13	Correct	11 ms	12032 KB	Output is correct
14	Correct	11 ms	12160 KB	Output is correct
15	Correct	11 ms	12160 KB	Output is correct
16	Correct	11 ms	12032 KB	Output is correct
17	Correct	11 ms	12032 KB	Output is correct
18	Correct	11 ms	12032 KB	Output is correct
19	Correct	11 ms	12032 KB	Output is correct
20	Correct	11 ms	12032 KB	Output is correct
21	Correct	11 ms	12032 KB	Output is correct
22	Correct	11 ms	12032 KB	Output is correct
23	Correct	11 ms	12032 KB	Output is correct
24	Correct	11 ms	12032 KB	Output is correct
25	Correct	11 ms	12160 KB	Output is correct
26	Correct	13 ms	12160 KB	Output is correct
27	Correct	13 ms	12160 KB	Output is correct
28	Correct	16 ms	12288 KB	Output is correct
29	Correct	13 ms	12288 KB	Output is correct
30	Correct	13 ms	12160 KB	Output is correct
31	Correct	11 ms	12032 KB	Output is correct
32	Correct	13 ms	12416 KB	Output is correct
33	Correct	11 ms	12032 KB	Output is correct
34	Correct	12 ms	12288 KB	Output is correct
35	Correct	13 ms	12288 KB	Output is correct
36	Incorrect	13 ms	12288 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Submission #227201

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0