Submission #40493

#	Time	Username	Problem	Language	Result	Execution time	Memory
40493		igzi	Tropical Garden (IOI11_garden)	C++14	69 / 100	5056 ms	35320 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define maxN 150005
#define INF LLONG_MAX
#define INT 1000000001

using namespace std;

vector <int> adj[maxN];
long long N,P,s,i,dis[2][maxN],k[2][maxN],c[2];
bool mar[maxN];

long long dfs(int n,int d){
long long y;
if(d>2*N) return INT;
if(adj[n].size()>0 && (adj[n][0]!=s || adj[n].size()==1)) {if(dis[0][n]!=INF) return dis[0][n];}
else {if(dis[1][n]!=INF) return dis[1][n];}
if(adj[n].size()>0 && (adj[n][0]!=s || adj[n].size()==1)) y=adj[n][0];
else y=adj[n][1];
if(adj[n][0]!=s || adj[n].size()==1) {
s=n;
dis[0][n]=dfs(y,d+1)+1;
if(n==adj[y][0]) k[0][n]=k[1][y];
else k[0][n]=k[0][y];
if(adj[n].size()==1){
    k[1][n]=k[0][n];
    dis[1][n]=dis[0][n];
}
return dis[0][n];}
else {
s=n;
dis[1][n]=dfs(y,d+1)+1;
if(n==adj[y][0]) k[1][n]=k[1][y];
else k[1][n]=k[0][y];
return dis[1][n];}
}
long long period(int x,int d){
if(d>3*N) return INF;
int y;
if(adj[x].size()>0 && (adj[x][0]!=s || adj[x].size()==1)) y=adj[x][0];
else y=adj[x][1];
if(y==P) {
if(x==adj[P][0]) {if(c[0]==-5) c[0]=1; else c[1]=1;}
else {if(c[0]==-5) c[0]=0; else c[1]=0;}
return d+1;
}
s=x;
return period(y,d+1);
}

void count_routes(int n,int m,int p,int r[][2],int q,int g[]){
N=n;
P=p;
for(i=0;i<m;i++){
    adj[r[i][0]].push_back(r[i][1]);
    adj[r[i][1]].push_back(r[i][0]);
}
for(i=0;i<n;i++){
    dis[0][i]=dis[1][i]=INF;
}
dis[0][p]=0;
dis[1][p]=0;
k[0][p]=0;
k[1][p]=1;
for(i=0;i<n;i++){
s=-5;
dis[0][i]=dfs(i,0);
s=adj[i][0];
dis[1][i]=dfs(i,0);
}
long long t1,t2;
s=-5;
c[0]=-5;
t1=period(p,0);
if(adj[p].size()>0) {
    s=adj[p][0];
    t2=period(p,0);
}
else t2=INF;
for(i=0;i<q;i++){
    long long ans=0;
    for(int j=0;j<n;j++){
        if(k[0][j]==0 && dis[0][j]<=g[i]){
            if(dis[0][j]==g[i]) {ans++; continue;}
            if(c[0]==0){
            if(t1!=INF && (g[i]-dis[0][j])%t1==0) {ans++; continue;}}
            else{
                if(c[1]==1){
                if((g[i]-dis[0][j]-t1)%t2==0) {ans++; continue;}}
                else{
                    if(t1!=INF && t2!=INF){
                    if((g[i]-dis[0][j])%(t1+t2)==0 || (g[i]-dis[0][j])%(t1+t2)==t1) {ans++; continue;}}
                }
            }
        }
        if(k[0][j]==1 && dis[0][j]<=g[i]){
            if(dis[0][j]==g[i]) {ans++; continue;}
            if(c[1]==1){
            if(t2!=INF && (g[i]-dis[0][j])%t2==0) {ans++; continue;}}
            else{
                if(c[0]==0){
                if((g[i]-dis[0][j]-t2)%t1==0) {ans++; continue;}}
                else{
                    if(t1!=INF && t2!=INF){
                    if((g[i]-dis[0][j])%(t1+t2)==0 || (g[i]-dis[0][j])%(t1+t2)==t2) {ans++; continue;}}
                }
            }
        }
    }
    answer(ans);
}
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31