oj.uz

답안 #1024746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024746 2024-07-16T09:54:08 Z LIF 참나무 (IOI23_beechtree) C++17
8 / 100
 97 ms 43580 KB 
#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

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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17756 KB Output is correct
2 Incorrect 3 ms 17880 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Incorrect 3 ms 17752 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Incorrect 3 ms 17752 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17756 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17756 KB Output is correct
6 Correct 3 ms 17756 KB Output is correct
7 Correct 3 ms 17756 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Incorrect 3 ms 17864 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
10 Halted 0 ms 0 KB -

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17756 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 59 ms 43580 KB Output is correct
6 Correct 59 ms 43464 KB Output is correct
7 Correct 3 ms 17876 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Correct 3 ms 17916 KB Output is correct
10 Correct 3 ms 17888 KB Output is correct
11 Correct 61 ms 27632 KB Output is correct
12 Correct 97 ms 25676 KB Output is correct

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17756 KB Output is correct
2 Incorrect 3 ms 17880 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17756 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17752 KB Output is correct
6 Correct 3 ms 17756 KB Output is correct
7 Correct 3 ms 17756 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Correct 3 ms 17756 KB Output is correct
10 Correct 3 ms 17864 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 17756 KB Output is correct
13 Correct 3 ms 17756 KB Output is correct
14 Correct 3 ms 17756 KB Output is correct
15 Correct 3 ms 17756 KB Output is correct
16 Incorrect 3 ms 17756 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17756 KB Output is correct
2 Incorrect 3 ms 17880 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 17756 KB Output is correct
2 Correct 3 ms 17756 KB Output is correct
3 Correct 3 ms 17756 KB Output is correct
4 Correct 3 ms 17756 KB Output is correct
5 Correct 3 ms 17752 KB Output is correct
6 Correct 3 ms 17756 KB Output is correct
7 Correct 3 ms 17756 KB Output is correct
8 Correct 3 ms 17756 KB Output is correct
9 Correct 3 ms 17756 KB Output is correct
10 Correct 3 ms 17864 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 17756 KB Output is correct
13 Correct 3 ms 17756 KB Output is correct
14 Correct 3 ms 17756 KB Output is correct
15 Correct 3 ms 17756 KB Output is correct
16 Incorrect 3 ms 17756 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17756 KB Output is correct
2 Incorrect 3 ms 17880 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -