| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1119084 | Marco_Escandon | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
vector<vector<ll>>cad;vector<vector<pair<ll,ll>>>v,cad2;
ll p;
pair<ll,ll> dfs(ll node, ll pl)
{
if(node==p) return {0,pl};
if(v[pl][node].first!=1e16) return v[pl][node];
v[pl][node]={1e17,pl};
v[pl][node]=dfs(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1));
v[pl][node].first++;
return v[pl][node];
}
pair<ll,ll> dfs2(ll node, ll pl)
{
if(node==p&&v[pl][node].x==1e17) return {0,0};
if(v[pl][node].first!=1e16) return v[pl][node];
v[pl][node]={1e17,pl};
v[pl][node]=dfs(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1));
v[pl][node].first++;
return v[pl][node];
}
ll dfs3(ll node, ll pl, ll k)
{
if(node==p&&k==0) return 1;
if(k<=0) return 0;
return dfs3(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1),k-1);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll n,m;
cin>>n>>m>>p;
cad.resize(n+2);
cad2.resize(n+2);
v.assign(4,vector<pair<ll,ll>>(n+2,{1e16,0}));
for(int i=0; i<m; i++)
{
ll a,b;
cin>>a>>b;
cad2[a].push_back({i,b});
cad2[b].push_back({i,a});
}
for(int i=0; i<=n; i++)
{
sort(cad2[i].begin(),cad2[i].end());
for(int j=0; j<min((ll)2,(ll)cad2[i].size()); j++)
cad[i].push_back(cad2[i][j].y);
}
for(int i=0; i<n; i++)
{
dfs(i,0);
dfs(i,min((ll)cad[i].size()-1,(ll)1));
}
dfs2(p,0);
dfs2(p,min((ll)cad[p].size()-1,(ll)1));
ll q;
cin>>q;
while(q--)
{
ll a;
cin>>a;
ll cont=0;
for(int i=0; i<n; i++)
{
if(a>=v[0][i].first||i==p)
{
ll b=a-v[0][i].first;
if(i==p) b=a;
cont+=((b%v[v[0][i].y][p].x)==0);
}
}
cout<<cont<<" ";
}
return 0;
}