Submission #227200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
227200	2020-04-26T13:28:26 Z	MKopchev	Mergers (JOI19_mergers)	C++14	10 / 100	126 ms	26232 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=1;i<=n;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	12032 KB	Output is correct
3	Correct	11 ms	12032 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	12160 KB	Output is correct
7	Correct	13 ms	12032 KB	Output is correct
8	Correct	11 ms	12032 KB	Output is correct
9	Correct	11 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	11 ms	12160 KB	Output is correct
13	Correct	11 ms	12160 KB	Output is correct
14	Correct	11 ms	12032 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	12160 KB	Output is correct
21	Correct	12 ms	12160 KB	Output is correct
22	Correct	11 ms	12160 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	12032 KB	Output is correct
3	Correct	11 ms	12032 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	12160 KB	Output is correct
7	Correct	13 ms	12032 KB	Output is correct
8	Correct	11 ms	12032 KB	Output is correct
9	Correct	11 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	11 ms	12160 KB	Output is correct
13	Correct	11 ms	12160 KB	Output is correct
14	Correct	11 ms	12032 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	12160 KB	Output is correct
21	Correct	12 ms	12160 KB	Output is correct
22	Correct	11 ms	12160 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	13 ms	12288 KB	Output is correct
27	Correct	13 ms	12288 KB	Output is correct
28	Correct	14 ms	12544 KB	Output is correct
29	Correct	14 ms	12416 KB	Output is correct
30	Correct	13 ms	12288 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	13 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	12032 KB	Output is correct
3	Correct	11 ms	12032 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	12160 KB	Output is correct
7	Correct	13 ms	12032 KB	Output is correct
8	Correct	11 ms	12032 KB	Output is correct
9	Correct	11 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	11 ms	12160 KB	Output is correct
13	Correct	11 ms	12160 KB	Output is correct
14	Correct	11 ms	12032 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	12160 KB	Output is correct
21	Correct	12 ms	12160 KB	Output is correct
22	Correct	11 ms	12160 KB	Output is correct
23	Correct	11 ms	12032 KB	Output is correct
24	Correct	11 ms	12032 KB	Output is correct
25	Correct	10 ms	12032 KB	Output is correct
26	Correct	65 ms	17916 KB	Output is correct
27	Correct	115 ms	17528 KB	Output is correct
28	Correct	20 ms	12288 KB	Output is correct
29	Correct	11 ms	12160 KB	Output is correct
30	Correct	11 ms	12160 KB	Output is correct
31	Correct	116 ms	17560 KB	Output is correct
32	Correct	14 ms	12416 KB	Output is correct
33	Correct	107 ms	26232 KB	Output is correct
34	Correct	118 ms	17528 KB	Output is correct
35	Incorrect	13 ms	12288 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	16368 KB	Output is correct
2	Correct	77 ms	17260 KB	Output is correct
3	Correct	13 ms	12288 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	11 ms	12032 KB	Output is correct
6	Correct	11 ms	12160 KB	Output is correct
7	Correct	12 ms	12288 KB	Output is correct
8	Correct	126 ms	18168 KB	Output is correct
9	Incorrect	13 ms	12288 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	12032 KB	Output is correct
3	Correct	11 ms	12032 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	12160 KB	Output is correct
7	Correct	13 ms	12032 KB	Output is correct
8	Correct	11 ms	12032 KB	Output is correct
9	Correct	11 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	11 ms	12160 KB	Output is correct
13	Correct	11 ms	12160 KB	Output is correct
14	Correct	11 ms	12032 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	12160 KB	Output is correct
21	Correct	12 ms	12160 KB	Output is correct
22	Correct	11 ms	12160 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	13 ms	12288 KB	Output is correct
27	Correct	13 ms	12288 KB	Output is correct
28	Correct	14 ms	12544 KB	Output is correct
29	Correct	14 ms	12416 KB	Output is correct
30	Correct	13 ms	12288 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	13 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 #227200

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