oj.uz

Submission #40492

# Submission time Handle Problem Language Result Execution time Memory
40492 2018-02-02T13:19:16 Z igzi Tropical Garden (IOI11_garden) C++14
49 / 100
 182 ms 31348 KB 
#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((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((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((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((g[i]-dis[0][j])%(t1+t2)==0 || (g[i]-dis[0][j])%(t1+t2)==t2) {ans++; continue;}
                }
            }
        }
    }
    answer(ans);
}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4088 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4088 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 8568 KB Output is correct
12 Correct 60 ms 11772 KB Output is correct
13 Correct 52 ms 20728 KB Output is correct
14 Correct 182 ms 31348 KB Output is correct
15 Correct 111 ms 14504 KB Output is correct
16 Correct 121 ms 23244 KB Output is correct
17 Correct 82 ms 11264 KB Output is correct
18 Incorrect 53 ms 11768 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4088 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3960 KB Output is correct
9 Correct 8 ms 4216 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 8568 KB Output is correct
12 Correct 60 ms 11772 KB Output is correct
13 Correct 52 ms 20728 KB Output is correct
14 Correct 182 ms 31348 KB Output is correct
15 Correct 111 ms 14504 KB Output is correct
16 Correct 121 ms 23244 KB Output is correct
17 Correct 82 ms 11264 KB Output is correct
18 Incorrect 53 ms 11768 KB Output isn't correct
19 Halted 0 ms 0 KB -