oj.uz

Submission #86608

# Submission time Handle Problem Language Result Execution time Memory
86608 2018-11-27T01:36:03 Z updown1 Tropical Garden (IOI11_garden) C++17
100 / 100
 3096 ms 24160 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
const ll MAXN=300000, INF = 1000000000;
int edges[MAXN][2], nex[MAXN];
bool open[MAXN];
vector<int> adj[MAXN]; /// value is index/2, want minimum next one
pair<int, int> ds[MAXN], df[MAXN];

void go11 (int at) {
    if (df[at].a != INF) return;
    if (open[at]) {df[at].a = -INF; return;}
    open[at] = true;
    go11 (nex[at]);
    /// set df[at]
    df[at].a = 1+df[nex[at]].a;
    open[at] = false;
}
void go12 (int at) {
    if (df[at].b != INF) return;
    if (open[at]) {df[at].b = -INF; return;}
    open[at] = true;
    go12 (nex[at]);
    /// set df[at]
    df[at].b = 1+df[nex[at]].b;
    open[at] = false;
}

void go21 (int at) {
    if (ds[at].a != INF) return;
    if (open[at]) {ds[at].a = -INF; return;}
    open[at] = true;
    go21 (nex[at]);
    /// set ds[at]
    ds[at].a = 1+ds[nex[at]].a;
    open[at] = false;
}
void go22 (int at) {
    if (ds[at].b != INF) return;
    if (open[at]) {ds[at].b = -INF; return;}
    open[at] = true;
    go22 (nex[at]);
    /// set ds[at]
    ds[at].b = 1+ds[nex[at]].b;
    open[at] = false;
}



void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    for (int j=M-1; j>=0; j--) {
        edges[2*j][0] = edges[2*j+1][1] = R[j][0];
        edges[2*j][1] = edges[2*j+1][0] = R[j][1];
        adj[R[j][0]].pb(2*j);
        adj[R[j][1]].pb(2*j+1);
    }
    ffi {
        sort(adj[i].begin(), adj[i].end());
        while (adj[i].size() > 2) adj[i].pop_back();
        if (adj[i].size() == 1) adj[i].pb(adj[i][0]); /// repeat the element
    }
    ffi {
        int x = adj[i][0]; /// edge
        int a = edges[x][1]; /// node
        int y = adj[a][0]; /// edge
        if (x/2 == y/2) nex[2*i] = 2*a+1;
        else nex[2*i] = 2*a;
        x = adj[i][1]; /// edge
        a = edges[x][1]; /// node
        y = adj[a][0]; /// edge
        //w<< i s a c x s y<<e;
        if (x/2 == y/2) nex[2*i+1] = 2*a+1;
        else nex[2*i+1] = 2*a;
        ds[2*i] = ds[2*i+1] = df[2*i] = df[2*i+1] = mp(INF, INF);
    }
//For (i, 0, 2*N) w<< i/2 c nex[i]/2 s nex[i]%2<<e;

    df[2*P].a = 0; /// we are already at P
    For (i, 0, 2*N) go11(i);
//For (i, 0, 2*N) w<< i/2 c df[i].a<<e;
    df[2*P].b = 1+ df[nex[2*P]].a;
    For (i, 0, 2*N) go12(i);
//For (i, 0, 2*N) w<< i/2 c df[i].b<<e;
    ds[2*P+1].a = 0; /// we are already at P
    For (i, 0, 2*N) go21(i);
//For (i, 0, 2*N) w<< i/2 c ds[i].a<<e;
    ds[2*P+1].b = 1+ ds[nex[2*P+1]].a;
    For (i, 0, 2*N) go22(i);
//For (i, 0, 2*N) w<< i/2 c ds[i].b<<e;


    for(int i=0; i<Q; i++) {
        int x = G[i];
        int out = 0;
        for (int j=0; j<2*N; j+= 2) {
            if (x == df[j].a) {out++; continue;}
            else if (x < df[j].a || df[j].a < 0 || df[j].b < 0) {}
            else {
//w<< j c df[j].a s df[j].b<<e;
                if (df[j].b != df[j].a && (x-df[j].a) % (df[j].b - df[j].a) == 0) {out++; continue;}
            }

            if (x == ds[j].a) {out++; continue;}
            else if (x < ds[j].a || ds[j].a < 0 || ds[j].b < 0) {}
            else {
//w<< j c ds[j].a s ds[j].b<<e;
                if (ds[j].b != ds[j].a && (x-ds[j].a) % (ds[j].b - ds[j].a) == 0) {out++; continue;}
            }
        }
//w<< "got" s i c out<<e;
        answer(out);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 9 ms 7528 KB Output is correct
4 Correct 8 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7584 KB Output is correct
9 Correct 12 ms 7800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 9 ms 7528 KB Output is correct
4 Correct 8 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7584 KB Output is correct
9 Correct 12 ms 7800 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 21 ms 9720 KB Output is correct
12 Correct 40 ms 11968 KB Output is correct
13 Correct 53 ms 18680 KB Output is correct
14 Correct 123 ms 21496 KB Output is correct
15 Correct 129 ms 21876 KB Output is correct
16 Correct 105 ms 19064 KB Output is correct
17 Correct 96 ms 18040 KB Output is correct
18 Correct 44 ms 11896 KB Output is correct
19 Correct 123 ms 21676 KB Output is correct
20 Correct 126 ms 21752 KB Output is correct
21 Correct 105 ms 18512 KB Output is correct
22 Correct 100 ms 17528 KB Output is correct
23 Correct 165 ms 22956 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7548 KB Output is correct
3 Correct 9 ms 7528 KB Output is correct
4 Correct 8 ms 7420 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7584 KB Output is correct
9 Correct 12 ms 7800 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 21 ms 9720 KB Output is correct
12 Correct 40 ms 11968 KB Output is correct
13 Correct 53 ms 18680 KB Output is correct
14 Correct 123 ms 21496 KB Output is correct
15 Correct 129 ms 21876 KB Output is correct
16 Correct 105 ms 19064 KB Output is correct
17 Correct 96 ms 18040 KB Output is correct
18 Correct 44 ms 11896 KB Output is correct
19 Correct 123 ms 21676 KB Output is correct
20 Correct 126 ms 21752 KB Output is correct
21 Correct 105 ms 18512 KB Output is correct
22 Correct 100 ms 17528 KB Output is correct
23 Correct 165 ms 22956 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 135 ms 9948 KB Output is correct
26 Correct 182 ms 11916 KB Output is correct
27 Correct 2001 ms 18544 KB Output is correct
28 Correct 1576 ms 21100 KB Output is correct
29 Correct 2247 ms 21376 KB Output is correct
30 Correct 1261 ms 18284 KB Output is correct
31 Correct 1046 ms 17308 KB Output is correct
32 Correct 194 ms 12024 KB Output is correct
33 Correct 1607 ms 21368 KB Output is correct
34 Correct 2148 ms 21676 KB Output is correct
35 Correct 1276 ms 18684 KB Output is correct
36 Correct 1579 ms 17636 KB Output is correct
37 Correct 1147 ms 22848 KB Output is correct
38 Correct 3096 ms 24160 KB Output is correct