oj.uz

Submission #40491

# Submission time Handle Problem Language Result Execution time Memory
40491 2018-02-02T13:03:14 Z igzi Tropical Garden (IOI11_garden) C++14
49 / 100
 59 ms 20788 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(dis[0][j]+t1==g[i]) {ans++; continue;}
            if(c[0]==0){
            if((g[i]-dis[0][j])%t1==0) {ans++; continue;}}
            else{
                if((g[i]-dis[0][j]-t1)%t2==0) {ans++; continue;}
            }
        }
        if(k[0][j]==1 && dis[0][j]<=g[i]){
            if(dis[0][j]==g[i]) {ans++; continue;}
            if(dis[0][j]+t2==g[i]) {ans++; continue;}
            if(c[1]==1){
            if((g[i]-dis[0][j])%t2==0) {ans++; continue;}}
            else{
                if((g[i]-dis[0][j]-t2)%t1==0) {ans++; continue;}
            }
        }
    }
    answer(ans);
}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4036 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 6 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4132 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3964 KB Output is correct
9 Correct 8 ms 4220 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4036 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 6 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4132 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3964 KB Output is correct
9 Correct 8 ms 4220 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 8412 KB Output is correct
12 Correct 59 ms 11688 KB Output is correct
13 Incorrect 52 ms 20788 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4036 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 6 ms 3932 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 6 ms 4132 KB Output is correct
7 Correct 5 ms 3832 KB Output is correct
8 Correct 6 ms 3964 KB Output is correct
9 Correct 8 ms 4220 KB Output is correct
10 Correct 5 ms 3832 KB Output is correct
11 Correct 28 ms 8412 KB Output is correct
12 Correct 59 ms 11688 KB Output is correct
13 Incorrect 52 ms 20788 KB Output isn't correct
14 Halted 0 ms 0 KB -