| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 137269 | KalasLavas | 친구 (IOI14_friend) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 2020 Free ram install
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//*/
std::mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
using namespace std;
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define y1 asjfkgasj
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define flsh '\n'<<flush
#define mp make_pair
#define mt make_tuple
#define sz size
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<ll>
#define deb(x) cout<< #x <<'='<< x <<flsh;
#define iii int,int,int
#define ull unsigned long long
#define intt long long
#define ld long double
#define dd double
#define setpre(x) fixed<<setprecision(x)
#define mmset(x,y) memset(x,y,sizeof(x))
intt n,c,h[1001],p[1001],col[1001],used[1001],ans,res1,res2;
vector<vector<int>>g;
void color(int v)
{
used[v]=1;
int x=1;
if(col[v]!=1 and col[v]!=2) while(1) col[0]=3-col[0];
for(int u : g[v])
if(!used[u])
{
col[u]=3-col[v];
color(u);
}
else if(col[v]==col[u]) while(1) col[0]=3-col[0];
return;
}
main()
{
IO;
cin>>n;
g.resize(n+1);
for(int i=0;i<n;i++)
{
cin>>c;
}
for(int i=1;i<n;i++)
cin>>h[i]>>p[i];
cout<<endl;
for(int i=1;i<n;i++)
{
int x=h[i];
if(p[i]==0)
{
g[x].pb(i);
g[i].pb(x);
//cout<<x<<' '<<i<<endl;
}
else if(p[i]==1)
{
g[i]=g[x];
for(int u : g[i])
{
g[u].pb(i);
//cout<<i<<' '<<u<<endl;
}
}
else
{
while(1) col[0]=3-col[0];
}
}
for(int i=0;i<n;i++)
if(!used[i])
{
mmset(col,0);
col[i]=1;
res1=res2=0;
color(i);
for(int j=0;j<n;j++)
{
if(col[j]==1) res1++;
if(col[j]==2) res2++;
//if(col[i]==0) while(1) col[0]=3-col[0];
//cout<<col[i]<<" \n"[i+1==n];
}
//cout<<res1<<","<<res2<<endl;
ans+=max(res1,res2);
}
cout<<ans;
return 0;
}
/*
33
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1
0 0
1 1
3 1
4 0
0 1
1 0
2 1
5 0
3 1
5 0
3 1
8 1
9 0
3 0
3 1
16 1
3 1
16 0
16 0
1 0
13 1
15 1
18 1
14 1
22 1
20 0
27 0
14 0
2 0
25 0
31 0
*/