oj.uz

Submission #86270

# Submission time Handle Problem Language Result Execution time Memory
86270 2018-11-25T21:15:36 Z updown1 Tropical Garden (IOI11_garden) C++17
0 / 100
 6 ms 4088 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
//#define int ll
const int MAXN=150000, INF = 1000000000;
int edges[2*MAXN][2];
bool open[MAXN][2];
vector<int> adj[MAXN]; /// value is index/2, want minimum next one
pair<int, int> ds[MAXN], df[MAXN];

void go12(int at);
void go11 (int at) {
    if (df[at].a != INF) return;
    if (open[at][0]) {df[at].a = -INF; return;}
    open[at][0] = true;

    int n1 = adj[at][0]; /// edge
    int x = edges[n1][1]; /// node
    //w<< "at11" c at<<e;
    go11 (x); go12(x);
    /// set df[at]
    int nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) df[at].a = 1+ds[x].a;
    else df[at].a = 1+df[x].a;
    open[at][0] = false;
}
void go12 (int at) {
    if (ds[at].a != INF) return;
    if (open[at][1]) {ds[at].a = -INF; return;}
    open[at][1] = true;

    int n1 = adj[at][1]; /// edge
    int x = edges[n1][1]; /// node
    //w<< "at12" c at<<e;
    go11 (x); go12(x);
    /// set ds[at]
    int nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) ds[at].a = 1+ds[x].a;
    else ds[at].a = 1+df[x].a;
    open[at][1] = false;
}

void go22(int at);
void go21 (int at) {
    if (df[at].b != INF) return;
    if (open[at][0]) {df[at].b = -INF; return;}
    open[at][0] = true;

    int n1 = adj[at][0]; /// edge
    int x = edges[n1][1]; /// node
    //w<< "at11" c at<<e;
    go21 (x); go22(x);
    /// set df[at]
    int nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) df[at].b = 1+ds[x].b;
    else df[at].b = 1+df[x].b;
    open[at][0] = false;
}
void go22 (int at) {
    if (ds[at].b != INF) return;
    if (open[at][1]) {ds[at].b = -INF; return;}
    open[at][1] = true;

    int n1 = adj[at][1]; /// edge
    int x = edges[n1][1]; /// node
    //w<< "at12" c at<<e;
    go21 (x); go22(x);
    /// set ds[at]
    int nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) ds[at].b = 1+ds[x].b;
    else ds[at].b = 1+df[x].b;
    open[at][1] = 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
        ds[i] = df[i] = mp(INF, INF);
    }
    ds[P].a = df[P].a = 0; /// we are already at P
    ffi go11(i), go12(i);
    //ffi w<< i c df[i].a s ds[i].a <<e;
    /// set df[P].b
    int n1 = adj[P][0]; /// edge
    int x = edges[n1][1]; /// node
    int nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) df[P].b = 1+ds[x].a;
    else df[P].b = 1+df[x].a;
    /// set ds[P].b
    n1 = adj[P][1]; /// edge
    x = edges[n1][1]; /// node
    nex = adj[x][0]/2; /// edge
    if (n1/2 == nex) ds[P].b = 1+ds[x].a;
    else ds[P].b = 1+df[x].a;

    ffi open[i][0] = open[i][1] = false;
    ffi go21(i), go22(i);
    //ffi w<< i c df[i].b s ds[i].b <<e;

    for(int i=0; i<Q; i++) {
        int x = G[i];
        int out = 0;
        ffj {
            if (x == df[j].a) out++;
            else if (x < df[j].a) {}
            else if ((x-df[j].a) % (df[j].b - df[j].a) == 0) out++;
        }
        answer(out);
    }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Incorrect 6 ms 4088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Incorrect 6 ms 4088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3932 KB Output is correct
3 Correct 5 ms 3932 KB Output is correct
4 Correct 5 ms 3960 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Incorrect 6 ms 4088 KB Output isn't correct
7 Halted 0 ms 0 KB -