oj.uz

Submission #27020

# Submission time Handle Problem Language Result Execution time Memory
27020 2017-07-08T16:59:29 Z repeating Tropical Garden (IOI11_garden) C++11
100 / 100
 4790 ms 68704 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
#define MAX_R  1000000
#define MAX_N 1000000
#define MAX_M 1000000

using namespace std;
const long long INF = 1e9+5e8;
const int MX=1500005;
int n,m,pos;
vector<pii> adj[MX];
pii dp[MX][2];
pii DP(int ver,int flag){
    if(ver==pos)
        R {0,flag};
    pii &ret=dp[ver][flag];
    if(ret.F!=-1)R ret;
    ret={INF,flag};
    if(flag==1&&adj[ver].SI==1)
        R ret=DP(ver,0);
    int node=adj[ver][flag].S,edge=adj[ver][flag].F;
    if(adj[node][0].F==edge)
        ret=DP(node,1);
    else ret=DP(node,0);
    ret.F++;
    R ret;
}
void build(){
    MEM(dp,-1);
    for(int i=0;i<n;i++){
        DP(i,0);
        DP(i,1);
    }
    int node=adj[pos][0].S,edge=adj[pos][0].F;
    if(adj[node][0].F==edge)
        dp[pos][0]=DP(node,1),dp[pos][0].F++;
    else dp[pos][0]=DP(node,0),dp[pos][0].F++;
    if(adj[pos].SI==1)
        dp[pos][1]=dp[pos][0];
    else{
        node=adj[pos][1].S,edge=adj[pos][1].F;
        if(adj[node][0].F==edge)
            dp[pos][1]=DP(node,1),dp[pos][1].F++;
        else dp[pos][1]=DP(node,0),dp[pos][1].F++;
    }
}
int way(int ver,int flag,int k){
    if(k<0)R 0;
    if(k==0)R 1;
    if(ver!=pos)R way(pos,dp[ver][flag].S,k-dp[ver][flag].F);
    int sum=INF;
    if(dp[pos][0].S==1&&dp[pos][1].S==0){
        sum=dp[pos][0].F+dp[pos][1].F;
    }
    if(dp[pos][flag].S==flag){
        sum=dp[pos][flag].F;
    }
    R way(pos,dp[pos][flag].S,(k-dp[pos][flag].F)%sum);
}
int solve(int dis){
    int ret=0;
    for(int i=0;i<n;i++){
        ret+=way(i,0,dis);
    }
    R ret;
}
void count_routes(int N, int M, int PP, int r[][2], int Q, int G[])
{
    n=N,m=M,pos=PP;
    for(int i=0;i<m;i++){
        adj[r[i][0]].pb({i,r[i][1]});
        adj[r[i][1]].pb({i,r[i][0]});
    }
    for(int i=0;i<n;i++){
        sort(all(adj[i]));
    }
    build();
    for(int i=0; i<Q; i++)
        answer(solve(G[i]));
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 59056 KB Output is correct
2 Correct 55 ms 59128 KB Output is correct
3 Correct 54 ms 59156 KB Output is correct
4 Correct 54 ms 59096 KB Output is correct
5 Correct 53 ms 59032 KB Output is correct
6 Correct 54 ms 59208 KB Output is correct
7 Correct 57 ms 59084 KB Output is correct
8 Correct 56 ms 59144 KB Output is correct
9 Correct 59 ms 59452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 59056 KB Output is correct
2 Correct 55 ms 59128 KB Output is correct
3 Correct 54 ms 59156 KB Output is correct
4 Correct 54 ms 59096 KB Output is correct
5 Correct 53 ms 59032 KB Output is correct
6 Correct 54 ms 59208 KB Output is correct
7 Correct 57 ms 59084 KB Output is correct
8 Correct 56 ms 59144 KB Output is correct
9 Correct 59 ms 59452 KB Output is correct
10 Correct 56 ms 59032 KB Output is correct
11 Correct 68 ms 60428 KB Output is correct
12 Correct 88 ms 62044 KB Output is correct
13 Correct 94 ms 68704 KB Output is correct
14 Correct 164 ms 67192 KB Output is correct
15 Correct 168 ms 67236 KB Output is correct
16 Correct 156 ms 66060 KB Output is correct
17 Correct 147 ms 65868 KB Output is correct
18 Correct 86 ms 61804 KB Output is correct
19 Correct 165 ms 66628 KB Output is correct
20 Correct 163 ms 66948 KB Output is correct
21 Correct 157 ms 66296 KB Output is correct
22 Correct 152 ms 65676 KB Output is correct
23 Correct 164 ms 67472 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 59056 KB Output is correct
2 Correct 55 ms 59128 KB Output is correct
3 Correct 54 ms 59156 KB Output is correct
4 Correct 54 ms 59096 KB Output is correct
5 Correct 53 ms 59032 KB Output is correct
6 Correct 54 ms 59208 KB Output is correct
7 Correct 57 ms 59084 KB Output is correct
8 Correct 56 ms 59144 KB Output is correct
9 Correct 59 ms 59452 KB Output is correct
10 Correct 56 ms 59032 KB Output is correct
11 Correct 68 ms 60428 KB Output is correct
12 Correct 88 ms 62044 KB Output is correct
13 Correct 94 ms 68704 KB Output is correct
14 Correct 164 ms 67192 KB Output is correct
15 Correct 168 ms 67236 KB Output is correct
16 Correct 156 ms 66060 KB Output is correct
17 Correct 147 ms 65868 KB Output is correct
18 Correct 86 ms 61804 KB Output is correct
19 Correct 165 ms 66628 KB Output is correct
20 Correct 163 ms 66948 KB Output is correct
21 Correct 157 ms 66296 KB Output is correct
22 Correct 152 ms 65676 KB Output is correct
23 Correct 164 ms 67472 KB Output is correct
24 Correct 58 ms 59000 KB Output is correct
25 Correct 324 ms 60468 KB Output is correct
26 Correct 445 ms 62012 KB Output is correct
27 Correct 3036 ms 67760 KB Output is correct
28 Correct 2343 ms 65488 KB Output is correct
29 Correct 4255 ms 65716 KB Output is correct
30 Correct 2759 ms 64980 KB Output is correct
31 Correct 3033 ms 64708 KB Output is correct
32 Correct 464 ms 61824 KB Output is correct
33 Correct 2315 ms 65996 KB Output is correct
34 Correct 4289 ms 66232 KB Output is correct
35 Correct 2804 ms 65272 KB Output is correct
36 Correct 4790 ms 64992 KB Output is correct
37 Correct 1950 ms 66556 KB Output is correct
38 Correct 4437 ms 68568 KB Output is correct