oj.uz

Submission #65638

# Submission time Handle Problem Language Result Execution time Memory
65638 2018-08-08T09:39:59 Z mhnd Tropical Garden (IOI11_garden) C++14
100 / 100
 3508 ms 38264 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 17144 KB Output is correct
2 Correct 18 ms 17232 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 18 ms 17060 KB Output is correct
5 Correct 18 ms 17132 KB Output is correct
6 Correct 18 ms 17144 KB Output is correct
7 Correct 17 ms 17016 KB Output is correct
8 Correct 18 ms 17208 KB Output is correct
9 Correct 20 ms 17288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17144 KB Output is correct
2 Correct 18 ms 17232 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 18 ms 17060 KB Output is correct
5 Correct 18 ms 17132 KB Output is correct
6 Correct 18 ms 17144 KB Output is correct
7 Correct 17 ms 17016 KB Output is correct
8 Correct 18 ms 17208 KB Output is correct
9 Correct 20 ms 17288 KB Output is correct
10 Correct 17 ms 17068 KB Output is correct
11 Correct 31 ms 19728 KB Output is correct
12 Correct 54 ms 21520 KB Output is correct
13 Correct 72 ms 29120 KB Output is correct
14 Correct 189 ms 32300 KB Output is correct
15 Correct 230 ms 32616 KB Output is correct
16 Correct 173 ms 27996 KB Output is correct
17 Correct 139 ms 26464 KB Output is correct
18 Correct 54 ms 21548 KB Output is correct
19 Correct 195 ms 32332 KB Output is correct
20 Correct 231 ms 32504 KB Output is correct
21 Correct 172 ms 28000 KB Output is correct
22 Correct 154 ms 26532 KB Output is correct
23 Correct 207 ms 33836 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17144 KB Output is correct
2 Correct 18 ms 17232 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 18 ms 17060 KB Output is correct
5 Correct 18 ms 17132 KB Output is correct
6 Correct 18 ms 17144 KB Output is correct
7 Correct 17 ms 17016 KB Output is correct
8 Correct 18 ms 17208 KB Output is correct
9 Correct 20 ms 17288 KB Output is correct
10 Correct 17 ms 17068 KB Output is correct
11 Correct 31 ms 19728 KB Output is correct
12 Correct 54 ms 21520 KB Output is correct
13 Correct 72 ms 29120 KB Output is correct
14 Correct 189 ms 32300 KB Output is correct
15 Correct 230 ms 32616 KB Output is correct
16 Correct 173 ms 27996 KB Output is correct
17 Correct 139 ms 26464 KB Output is correct
18 Correct 54 ms 21548 KB Output is correct
19 Correct 195 ms 32332 KB Output is correct
20 Correct 231 ms 32504 KB Output is correct
21 Correct 172 ms 28000 KB Output is correct
22 Correct 154 ms 26532 KB Output is correct
23 Correct 207 ms 33836 KB Output is correct
24 Correct 18 ms 17088 KB Output is correct
25 Correct 151 ms 19856 KB Output is correct
26 Correct 209 ms 21564 KB Output is correct
27 Correct 3508 ms 29132 KB Output is correct
28 Correct 1437 ms 32972 KB Output is correct
29 Correct 2041 ms 33008 KB Output is correct
30 Correct 1295 ms 28508 KB Output is correct
31 Correct 1189 ms 27320 KB Output is correct
32 Correct 231 ms 22132 KB Output is correct
33 Correct 1456 ms 33092 KB Output is correct
34 Correct 1983 ms 33392 KB Output is correct
35 Correct 1308 ms 28764 KB Output is correct
36 Correct 1977 ms 27320 KB Output is correct
37 Correct 1173 ms 34612 KB Output is correct
38 Correct 3075 ms 38264 KB Output is correct