| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1032908 | tosivanmak | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
const ll maxn=100005;
#define DEBUG if(0)
ll cyc0=-1,cyc1=-1;
ll n,m,p;
pll bl[maxn][2][21];
ll accum[maxn][2][21];
// 0: no max, 1: yes max
vector<ll>adj[maxn];
bool vis[maxn][2];
map<ll,ll>cnt;
vector<ll>for0[300005],for1[300005];
void preprocessing(ll node, ll id){
DEBUG cout<<"node id "<<node<<" "<<id<<'\n';
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
if(bl[i][j][0]==mp(node,id))accum[i][j][0]=1;
else accum[i][j][0]=0;
}
}
for(int k=1;k<=20;k++){
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
accum[i][j][k]=accum[i][j][k-1]+accum[bl[i][j][k-1].first][bl[i][j][k-1].second][k-1];
// DEBUG cout<<"accumulative "<<i<<" "<<j<<" "<<k<<" "<<accum[i][j][k]<<'\n';
}
}
}
}
ll find(ll curi, ll curj, ll node, ll id){
ll cn=0;
for(int j=20;j>=0;j--){
if(accum[curi][curj][j]==0){
ll nxti=bl[curi][curj][j].first,nxtj=bl[curi][curj][j].second;
curi=nxti,curj=nxtj;
cn+=(1<<j);
}
}
cn++; return cn;
}
void solve(ll node, ll id){
DEBUG cout<<node<<" "<<id<<'\n';
for(int i=1;i<=n;i++){
for(int j=1;j<2;j++){
if(accum[i][j][20]==0)continue;
if(accum[i][j][20]==1){
ll steps=find(i,j,node,id);
cnt[steps]++;
DEBUG cout<<"no cycle "<<i<<" "<<j<<" "<<steps<<'\n';
}
else{
ll steps=find(i,j,node,id);
ll steps2=find(node,id,node,id);
DEBUG cout<<"yes cycle "<<i<<" "<<j<<" "<<steps<<" "<<steps2<<'\n';
if(id==0)cyc0=steps2;
else cyc1=steps2;
if(id==0)for0[steps%steps2].push_back(steps);
else for1[steps%steps2].push_back(steps);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>p;
p++;
for(int i=1;i<=m;i++){
ll u,v;
cin>>u>>v;u++,v++;
adj[u].pb(v);adj[v].pb(u);
}
for(int i=1;i<=n;i++){
if(adj[i].size()==0){
bl[i][0][0]=bl[i][1][0]=mp(-1,-1);
continue;
}
else if(adj[i].size()==1){
ll nxt=adj[i][0];
if(adj[nxt][0]==i){
bl[i][0][0]=bl[i][1][0]=mp(nxt,0);
}
else{
bl[i][0][0]=bl[i][1][0]=mp(nxt,1);
}
}
else{
ll nxt=adj[i][0];
if(adj[nxt][0]==i){
bl[i][1][0]=mp(nxt,0);
}
else{
bl[i][1][0]=mp(nxt,1);
}
nxt=adj[i][1];
if(adj[nxt][0]==i){
bl[i][0][0]=mp(nxt,0);
}
else{
bl[i][0][0]=mp(nxt,1);
}
}
}
for(int k=1;k<=20;k++){
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
bl[i][j][k]=bl[bl[i][j][k-1].first][bl[i][j][k-1].second][k-1];
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<2;j++){
// DEBUG cout<<i<<" "<<j<<": "<<bl[i][j][0].first<<" "<<bl[i][j][0].second<<"\n";
// for(int k=0;k<2;k++){
// DEBUG cout<<i<<" "<<j<<" "<<k<<" "<<bl[i][j][k].first<<" "<<bl[i][j][k].second<<'\n';
// }
}
}
preprocessing(p,0);
solve(p,0);
preprocessing(p,1);
solve(p,1);
for(int i=0;i<300005;i++){
if(for0[i].size())sort(for0[i].begin(),for0[i].end());
if(for1[i].size())sort(for1[i].begin(),for1[i].end());
}
ll q;
cin>>q;
while(q--){
ll g;
cin>>g;
ll ans=0;
ans+=cnt[g];
if(cyc0!=-1){
ll bruh=g%cyc0;
if(for0[bruh].size()!=0){
if(for0[bruh][0]>g){
}
else{
ll l=0,r=for0[bruh].size()-1;
while(l<r){
ll mid=(l+r+1)>>1;
if(for0[bruh][mid]<=g)l=mid;
else r=mid-1;
}
ans+=(l+1);
}
}
}
if(cyc1!=-1){
ll bruh=g%cyc1;
if(for1[bruh].size()!=0){
if(for1[bruh][0]>g){
}
else{
ll l=0,r=for1[bruh].size()-1;
while(l<r){
ll mid=(l+r+1)>>1;
if(for1[bruh][mid]<=g)l=mid;
else r=mid-1;
}
ans+=(l+1);
}
}
}
cout<<ans<<'\n';
}
}