| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 554562 | hegel123 | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 150005;
int n, m, x, a, b,q ;
vector <pair<int, int>> G1[maxn];
vector <int> V[2*maxn+10];
vector <int> Vodw[2*maxn+10];
vector <int> Vpel[2*maxn+10];
int sp[2*maxn+10];
bool czycykl[2*maxn+10];
bool o[2*maxn+10];
bool czyzn[2*maxn+10];
int akt;
int roz[2*maxn+10];
int odl[2][2*maxn+10];
int tab[2][2*maxn+10];
int pref[2][2*maxn+10];
void wczytaj(){
cin>>n>>m>>x; int w=m+10;
for(int i=0; i<m; i++){
cin>>a>>b;
G1[a].push_back({b, w});
G1[b].push_back({a, w});
w--;
}
}
bool cmp(pair<int, int>& a, pair<int, int>& b){return a.second>b.second;}
int sas;
void con(){
for(int i=0; i<n; i++)sort(G1[i].begin(), G1[i].end(), cmp);
for(int i=0; i<n; i++){
sas = G1[i][0].first;
if(G1[sas][0].first == i)V[i].push_back(sas+maxn);
else V[i].push_back(sas);
if(G1[i].size() == 1) sas = G1[i][0].first;
else sas = G1[i][1].first;
if(G1[sas][0].first == i)V[i+maxn].push_back(sas+maxn);
else V[i+maxn].push_back(sas);
}
}
void fill(){
for(int i=0; i<n; i++){
Vodw[V[i][0]].push_back(i);
Vpel[V[i][0]].push_back(i);
Vpel[i].push_back(V[i][0]);
Vodw[V[i+maxn][0]].push_back(i+maxn);
Vpel[V[i+maxn][0]].push_back(i+maxn);
Vpel[i+maxn].push_back(V[i+maxn][0]);
}
}
int t = 1;
void DFSsp(int ind){
sp[ind]=t;
for(auto v : Vpel[ind]){
if(sp[v]==0)DFSsp(v);
}
}
void DFS2(int ind){
if(czycykl[ind])return;
else{
akt++;
czyzn[sp[ind]]=true;
czycykl[ind]=true;
DFS2(V[ind][0]);
}
}
void DFS(int ind){
if(czycykl[ind])return;
o[ind]=true;
sas = V[ind][0];
if(!o[sas])DFS(sas);
else {
if(!czyzn[sp[ind]]){
DFS2(sas);
roz[sp[ind]]=akt;
akt=0;
}
}
}
void BFS(int ind, int zj){
queue <int> Q; Q.push(ind);
while(!Q.empty()){
int s = Q.front(); Q.pop();
for(auto v : Vodw[s]){
if(v==ind)continue;
odl[zj][v]=odl[zj][s]+1;
Q.push(v);
}
}
}
void solve(){
for(int i=0; i<n; i++){
if(sp[i]==0){DFSsp(i); t++;}
if(sp[i+maxn]==0){DFSsp(i+maxn); t++;}
}
for(int i=0; i<n; i++){
if(!o[i])DFS(i);
if(!o[i+maxn])DFS(i+maxn);
}
BFS(x, 0);
BFS(x+maxn, 1);
for(int i=0; i<n; i++){
tab[0][odl[0][i]]++;
tab[1][odl[1][i]]++;
}
int dl = roz[sp[x]];
for(int i=0; i<2*maxn+9; i++){
if(i>dl)pref[0][i]=pref[0][i-dl];
pref[0][i]+=tab[0][i];
}
dl = roz[sp[x+maxn]];
for(int i=0; i<2*maxn+9; i++){
if(i>dl)pref[1][i]=pref[1][i-dl];
pref[1][i]+=tab[1][i];
}
}
int zap(int z){
int wynik = 0;
if(!czycykl[x]){
wynik+=tab[0][min(z, 2*maxn+9)];
}
if(!czycykl[x+maxn]){
wynik+=tab[1][min(z, 2*maxn+9)];
}
if(czycykl[x]){
int dl = roz[sp[x]];
if(z<dl){wynik+=tab[0][min(z, 2*maxn+9)];}
else{
if(z%dl==0)wynik++;
int reszta = z%dl;
//for(int i = reszta; i<=min(z, 2*maxn+9); i+=dl){if(i!=0)wynik+=tab[0][i];}
wynik+=pref[0][min(z, reszta + ((2*maxn+9-reszta)/dl)*dl + reszta )];
}
}
if(czycykl[x+maxn]){
int dl = roz[sp[x+maxn]];
if(z<dl){wynik+=tab[1][min(z, 2*maxn+9)];}
else{
int reszta = z%dl;
//for(int i = reszta; i<=min(z, 2*maxn+9); i+=dl){if(i!=0)wynik+=tab[1][i];}
wynik+=pref[1][min(z, reszta + ((2*maxn+9-reszta)/dl)*dl + reszta )];
}
}
return wynik;
}
int idz(int ind, int dl, int pop){
//cout<<ind<<" ";
if(dl==0)return ind;
if(pop == G1[ind][0].first && G1[ind].size()>1)return idz(G1[ind][1].first, dl-1, ind);
return idz(G1[ind][0].first, dl-1, ind);
}
int zapbrut(int dl){
int wynik=0;
for(int i=0; i<n; i++){
//cout<<"wyruszamy: ";
if(idz(i, dl, -1)==x)wynik++;
//cout<<endl;
}
return wynik;
}
bool cmp1(pair<int, int>& a, pair <int, int>& b){return a.second>b.second;}
int brutt(){
int a;
while(q--){
cin>>a;
cout<<zapbrut(a)<<" ";
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
wczytaj();
con();
fill();
solve();
//cout<<"wypisywanie: "<<pref[1][3];
cin>>q;
//if(n<=1000 && m<= 10000 && q ==1){brutt(); return 0;}
while(q--){
cin>>a;
cout<<zap(a)<<" ";
}
return 0;
}