# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
315671 | Dymo | 무제 (POI11_dyn) | C++17 | 3086 ms | 44232 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=3e5+100;
const ll mod =1e9 + 7 ;
const ll base=3e9;
ll nw[maxn];
ll a[maxn];
ll cnt[maxn];
ll par[maxn];
ll n, m;
ll cocan[maxn];
ll colua[maxn];
bool chk1[maxn];
bool chk2[maxn];
vector<ll> adj[maxn];
vector<ll> adj1[maxn];
void dfs(ll u,ll par1)
{
par[u]=par1;
for (auto to:adj[u])
{
if (to==par1)
continue;
cnt[u]++;
dfs(to,u);
}
}
bool chk(ll mid)
{
queue<ll> q;
for (int i=1; i<=n; i++)
{
cnt[i]=0;
chk1[i]=0;
chk2[i]=0;
cocan[i]=0;
colua[i]=0;
adj1[i].clear();
}
dfs(1,0);
for (int i=1; i<=n; i++)
{
if (cnt[i]==0)
{
q.push(i);
// cout <<i<<endl;
}
}
ll ans=0;
while (!q.empty())
{
auto p=q.front();
q.pop();
bool chklua=false;
bool chkcan=false;
ll solua=0;
ll socan=0;
/*4 1
1 1 1 0
2 3
3 4
1 3*/
while (1)
{
// cout <<p<<endl;
if (chkcan==true)
{
socan++;
/*if (p==1)
{
cout <<"WTF"<<endl;
}*/
}
if (chklua==true)
{
solua--;
}
if (solua<0)
{
solua=0;
chklua=0;
}
if (chk1[p]==true)
{
chklua=true;
solua=max(solua,colua[p]);
}
if (chk2[p]==true)
{
/* if (p==1)
{
cout <<"WTF"<<endl;
}*/
chkcan=true;
socan=max(socan,cocan[p]);
}
if (a[p])
{
chkcan=true;
socan=max(socan,0);
}
if (chkcan&&chklua)
{
if (solua>=socan)
{
chkcan=false;
socan=0;
}
}
/* if (p==1)
{
cout <<cocan[p]<<" "<<chk2[p]<<" "<<colua[p]<<" "<<chk1[p]<<" "<<p<<" "<<chkcan<<" "<<socan<<endl;
}*/
if (chkcan&&socan==mid)
{
chklua=true;
solua=mid;
//cout <<p<<endl;
ans++;
// cout <<p<<endl;
socan=0;
chkcan=0;
}
chk1[p]=chklua;
chk2[p]=chkcan;
colua[p]=solua;
cocan[p]=socan;
for (auto to:adj1[p])
{
chkcan=chk2[to];
chklua=chk1[to];
solua=colua[to];
socan=cocan[to];
if (chkcan==true)
{
socan++;
}
if (chklua==true)
{
solua--;
}
if (solua<0)
{
solua=0;
chklua=0;
}
if (chk1[p]==true)
{
chklua=true;
solua=max(solua,colua[p]);
}
if (chk2[p]==true)
{
chkcan=true;
socan=max(socan,cocan[p]);
}
if (a[p])
{
chkcan=true;
socan=max(socan,0);
}
if (chkcan&&chklua)
{
if (solua>=socan)
{
chkcan=false;
socan=0;
}
}
if (chkcan&&socan==mid)
{
chklua=true;
solua=mid;
// cout <<p<<" "<<to<<" "<<colua[p]<<endl;
ans++;
socan=false;
chkcan=false;
}
chk1[p]=chklua;
chk2[p]=chkcan;
colua[p]=solua;
cocan[p]=socan;
// cout <<to<<" "<<p<<"ok"<<" "<<chk2[p]<<" "<<chkcan<<endl;
// if (p==3) cout <<chk2[p]<<" "<<chkcan<<endl;
}
/* if (p==3)
{
cout <<cocan[p]<<" "<<chk2[p]<<" "<<colua[p]<<" "<<chk1[p]<<" "<<par[p]<<" "<<chkcan<<endl;
}*/
if (par[p]==-1)
break;
cnt[par[p]]--;
if (cnt[par[p]])
{
adj1[par[p]].pb(p);
break;
}
//cout <<p<<"nxt"<<endl;
p=par[p];
}
}
for (int i=1; i<=n; i++)
{
// cout <<cocan[i]<<" "<<chk2[i]<<" "<<colua[i]<<" "<<chk1[i]<<" "<<i<<endl;
}
// cout <<ans<<endl;
// cout <<colua[3]<<" "<<cocan[3]<<" "<<chk1[3]<<" "<<chk2[3]<<endl;
ans=ans+chk2[1];
if (ans<=m)
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("girth.t", "r"))
{
freopen("girth.inp", "r", stdin);
freopen("girth.ans", "w", stdout) ;
}
cin>>n>>m ;
for (int i=1; i<=n; i++)
{
cin>>a[i];
}
for (int i=1; i<=n-1; i++)
{
ll x, y;
cin>>x>> y;
adj[x].pb(y);
adj[y].pb(x);
}
ll l=0, h= 1e9;
while (l<=h)
{
ll mid=(l+h)/2;
if (chk(mid))
{
h=mid-1;
}
else
{
l=mid+1;
}
}
cout <<l;
// cout <<chk(1);
/* 6
1
0 0 0 0 1 1
1 2
2 3
2 4
3 5
4 6*/
/*6
1
0 0 0 0 1 1
1 2
2 3
2 4
3 5
3 6*/
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |