oj.uz

Submission #65639

# Submission time Handle Problem Language Result Execution time Memory
65639 2018-08-08T09:40:51 Z mhnd Tropical Garden (IOI11_garden) C++11
100 / 100
 3391 ms 38256 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 17272 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 17 ms 17128 KB Output is correct
5 Correct 17 ms 17104 KB Output is correct
6 Correct 19 ms 17268 KB Output is correct
7 Correct 17 ms 17092 KB Output is correct
8 Correct 18 ms 17156 KB Output is correct
9 Correct 20 ms 17192 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 17272 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 17 ms 17128 KB Output is correct
5 Correct 17 ms 17104 KB Output is correct
6 Correct 19 ms 17268 KB Output is correct
7 Correct 17 ms 17092 KB Output is correct
8 Correct 18 ms 17156 KB Output is correct
9 Correct 20 ms 17192 KB Output is correct
10 Correct 17 ms 17116 KB Output is correct
11 Correct 32 ms 19832 KB Output is correct
12 Correct 58 ms 21552 KB Output is correct
13 Correct 72 ms 29120 KB Output is correct
14 Correct 196 ms 32220 KB Output is correct
15 Correct 225 ms 32612 KB Output is correct
16 Correct 167 ms 28000 KB Output is correct
17 Correct 142 ms 26460 KB Output is correct
18 Correct 55 ms 21552 KB Output is correct
19 Correct 213 ms 32968 KB Output is correct
20 Correct 230 ms 33220 KB Output is correct
21 Correct 162 ms 28292 KB Output is correct
22 Correct 161 ms 27196 KB Output is correct
23 Correct 206 ms 34452 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 17272 KB Output is correct
3 Correct 18 ms 17248 KB Output is correct
4 Correct 17 ms 17128 KB Output is correct
5 Correct 17 ms 17104 KB Output is correct
6 Correct 19 ms 17268 KB Output is correct
7 Correct 17 ms 17092 KB Output is correct
8 Correct 18 ms 17156 KB Output is correct
9 Correct 20 ms 17192 KB Output is correct
10 Correct 17 ms 17116 KB Output is correct
11 Correct 32 ms 19832 KB Output is correct
12 Correct 58 ms 21552 KB Output is correct
13 Correct 72 ms 29120 KB Output is correct
14 Correct 196 ms 32220 KB Output is correct
15 Correct 225 ms 32612 KB Output is correct
16 Correct 167 ms 28000 KB Output is correct
17 Correct 142 ms 26460 KB Output is correct
18 Correct 55 ms 21552 KB Output is correct
19 Correct 213 ms 32968 KB Output is correct
20 Correct 230 ms 33220 KB Output is correct
21 Correct 162 ms 28292 KB Output is correct
22 Correct 161 ms 27196 KB Output is correct
23 Correct 206 ms 34452 KB Output is correct
24 Correct 19 ms 17084 KB Output is correct
25 Correct 198 ms 20084 KB Output is correct
26 Correct 208 ms 21848 KB Output is correct
27 Correct 3391 ms 29388 KB Output is correct
28 Correct 1433 ms 32468 KB Output is correct
29 Correct 2059 ms 32880 KB Output is correct
30 Correct 1308 ms 28008 KB Output is correct
31 Correct 1195 ms 26540 KB Output is correct
32 Correct 217 ms 21556 KB Output is correct
33 Correct 1458 ms 32308 KB Output is correct
34 Correct 1990 ms 32608 KB Output is correct
35 Correct 1300 ms 27992 KB Output is correct
36 Correct 1975 ms 26548 KB Output is correct
37 Correct 1135 ms 33848 KB Output is correct
38 Correct 3054 ms 38256 KB Output is correct