Submission #1024746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024746		LIF	Beech Tree (IOI23_beechtree)	C++17	8 / 100	97 ms	43580 KiB

beechtree

#include "beechtree.h"
#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
vector<int> vv[500005];
int maxdepth[500005];
int depth[500005];
int ans[500005];
void dfs(int now,int dep)
{
    maxdepth[now] = depth[now] = dep;
    for(auto it : vv[now])
    {
        dfs(it,dep+1);
        maxdepth[now] = max(maxdepth[now],maxdepth[it]);
    }
    return;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
    for(int i=1;i<P.size();i++)
    {
        int father = P[i];
        int son = i;
        vv[father].push_back(son);
    }
    dfs(0,1);
    // ???€憭???暺?
    for(int i=0;i<N;i++)
    {
        if(maxdepth[i] == depth[i])ans[i] = 1;
        else
        {
            if(maxdepth[i] == depth[i] + 1)
            {
                map<int,int> mp;
                bool flag = true;
                for(auto it : vv[i])
                {
                    int nowcolor = C[it];
                    if(mp[nowcolor] != 0)
                    {
                        flag = false;
                        break;
                    }
                    else mp[nowcolor] = 1;
                }
                if(flag == true)ans[i] = 1;
                else ans[i] = 0;
            }
            else
            {
                if(maxdepth[i] == depth[i] + 2)
                {
                    map<int,int> mp;
                    bool flag = true;
                    for(auto it : vv[i]) //擐?靽??????脤???詨?嚗?
                    {
                        int nowcolor = C[it];
                        if(mp[nowcolor] != 0)
                        {
                            flag = false;
                            break;
                        }
                        else mp[nowcolor] = 1;
                    }
                    int cnt = 0;
                    for(auto it : vv[i])
                    {
                        if(vv[it].size() >= 1)
                        {
                            cnt++;
                            map<int,int> mp2;
                            for(auto j : vv[it])
                            {
                            	int nowcolor = C[j];
                            	if(mp2[nowcolor] != 0)
                            	{
                            		flag = false;
                            		break;
								}
								else mp2[nowcolor] = 1;
                            	if(mp[nowcolor] == 0)flag = false;
							}
                        }
                    }
                    if(cnt >= 2)flag = false;
                    if(flag == true)ans[i] = 1;
                    else ans[i] = 0;
                }
                else ans[i] = 0;
            }
        }
    }
    vector<int> temp;
    for(int i=0;i<N;i++)
    {
        temp.push_back(ans[i]);
    }
   /* for(int i=0;i<100;i++)if(ans[i] == 0)cout<<i<<endl;
    
    cout<<maxdepth[49]<<" "<<depth[49]<<" "<<ans[49]<<endl;
    for(auto it : vv[49])
    {
    	cout<<it<<" "<<vv[it].size()<<" "<<C[it]<<" "<<endl;
    	cout<<"son"<<endl;
    	if(vv[it].size() == 2)cout<<vv[it][0]<<" "<<C[vv[it][0]]<<endl;
    	if(vv[it].size() == 2)cout<<vv[it][1]<<" "<<C[vv[it][1]]<<endl;
    	cout<<endl;
	}
	*/
    return temp;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=1;i<P.size();i++)
      |                 ~^~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 8 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12