oj.uz

Submission #65640

# Submission time Handle Problem Language Result Execution time Memory
65640 2018-08-08T09:41:35 Z mhnd Tropical Garden (IOI11_garden) C++17
100 / 100
 3393 ms 38268 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

vector<int> g[N],g2[N];
int n,d[2][N],to[N],fr[2],frd[2][2];
bool vis[N];

bool go(int t,int rem){
    if(!rem)return 1;
    if(rem < 0 || fr[t]==-1)return 0;
    if(fr[t] == t)return (rem%frd[t][t])==0;
    rem %= frd[t][!t] + frd[!t][t];
    return go(!t,rem - frd[t][!t]);
}

void bfs(int s,int t){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    d[t][s] = 0;
    while(q.size()){
        int u = q.front();
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i=0;i<(int)g2[u].size();i++){
            int v = g2[u][i];
            if(d[t][v] != -1)continue;
            d[t][v] = d[t][u] + 1;
            q.push(v);
        }
    }
}

void cycle(int s,int t){
    memset(vis,0,sizeof(vis));
    int cur = to[s];
    int d = 1;
    while(!vis[cur]){
        vis[cur] = 1;
        if(cur == s%n){
            fr[t] = 0;
            frd[t][0] = d;
            break;
        }
        if(cur == (s%n)+n){
            fr[t] = 1;
            frd[t][1] = d;
            break;
        }
        d++;
        cur = to[cur];
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N;
    for(int i=0;i<M;i++){
        int u = R[i][0];
        int v = R[i][1];
        if(g[u].size() < 2)g[u].push_back(v);
        if(g[v].size() < 2)g[v].push_back(u);
    }
    for(int i=n;i<2*n;i++){
        g[i] = g[i-n];
        if(g[i].size() == 2)swap(g[i][0],g[i][1]);
    }
    for(int i=0;i<2*n;i++){
        int v = g[i][0];
        if(g[v][0] == i%n)v += n;
        to[i] = v;
        g2[v].push_back(i);
    }
    memset(d,-1,sizeof(d));
    memset(frd,-1,sizeof(frd));
    fr[0] = fr[1] = -1;
    bfs(P,0);
    bfs(P+n,1);
    cycle(P,0);
    cycle(P+n,1);
    for(int i=0;i<Q;i++){
        int dist = G[i];
        int ans = 0;
        for(int j=0;j<n;j++){
            bool o=0,t=0;
            if(d[0][j] != -1){
                int rem = dist - d[0][j];
                o = go(0,rem);
            }
            if(d[1][j] != -1){
                int rem = dist - d[1][j];
                t = go(1,rem);
            }
            ans += o|t;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17116 KB Output is correct
2 Correct 18 ms 17248 KB Output is correct
3 Correct 18 ms 17172 KB Output is correct
4 Correct 17 ms 17016 KB Output is correct
5 Correct 17 ms 17144 KB Output is correct
6 Correct 18 ms 17284 KB Output is correct
7 Correct 18 ms 17016 KB Output is correct
8 Correct 18 ms 17168 KB Output is correct
9 Correct 19 ms 17228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17116 KB Output is correct
2 Correct 18 ms 17248 KB Output is correct
3 Correct 18 ms 17172 KB Output is correct
4 Correct 17 ms 17016 KB Output is correct
5 Correct 17 ms 17144 KB Output is correct
6 Correct 18 ms 17284 KB Output is correct
7 Correct 18 ms 17016 KB Output is correct
8 Correct 18 ms 17168 KB Output is correct
9 Correct 19 ms 17228 KB Output is correct
10 Correct 17 ms 17116 KB Output is correct
11 Correct 31 ms 19960 KB Output is correct
12 Correct 51 ms 22088 KB Output is correct
13 Correct 73 ms 30012 KB Output is correct
14 Correct 193 ms 33232 KB Output is correct
15 Correct 227 ms 33644 KB Output is correct
16 Correct 167 ms 29264 KB Output is correct
17 Correct 151 ms 27808 KB Output is correct
18 Correct 50 ms 21796 KB Output is correct
19 Correct 191 ms 32784 KB Output is correct
20 Correct 233 ms 33108 KB Output is correct
21 Correct 176 ms 28384 KB Output is correct
22 Correct 158 ms 26996 KB Output is correct
23 Correct 202 ms 34316 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17116 KB Output is correct
2 Correct 18 ms 17248 KB Output is correct
3 Correct 18 ms 17172 KB Output is correct
4 Correct 17 ms 17016 KB Output is correct
5 Correct 17 ms 17144 KB Output is correct
6 Correct 18 ms 17284 KB Output is correct
7 Correct 18 ms 17016 KB Output is correct
8 Correct 18 ms 17168 KB Output is correct
9 Correct 19 ms 17228 KB Output is correct
10 Correct 17 ms 17116 KB Output is correct
11 Correct 31 ms 19960 KB Output is correct
12 Correct 51 ms 22088 KB Output is correct
13 Correct 73 ms 30012 KB Output is correct
14 Correct 193 ms 33232 KB Output is correct
15 Correct 227 ms 33644 KB Output is correct
16 Correct 167 ms 29264 KB Output is correct
17 Correct 151 ms 27808 KB Output is correct
18 Correct 50 ms 21796 KB Output is correct
19 Correct 191 ms 32784 KB Output is correct
20 Correct 233 ms 33108 KB Output is correct
21 Correct 176 ms 28384 KB Output is correct
22 Correct 158 ms 26996 KB Output is correct
23 Correct 202 ms 34316 KB Output is correct
24 Correct 19 ms 17080 KB Output is correct
25 Correct 153 ms 20088 KB Output is correct
26 Correct 208 ms 22044 KB Output is correct
27 Correct 3393 ms 29512 KB Output is correct
28 Correct 1475 ms 32460 KB Output is correct
29 Correct 2055 ms 33516 KB Output is correct
30 Correct 1298 ms 28668 KB Output is correct
31 Correct 1196 ms 27092 KB Output is correct
32 Correct 218 ms 21724 KB Output is correct
33 Correct 1440 ms 32832 KB Output is correct
34 Correct 2001 ms 33124 KB Output is correct
35 Correct 1319 ms 29020 KB Output is correct
36 Correct 1987 ms 27572 KB Output is correct
37 Correct 1132 ms 33852 KB Output is correct
38 Correct 3029 ms 38268 KB Output is correct