oj.uz

Submission #95115

# Submission time Handle Problem Language Result Execution time Memory
95115 2019-01-27T12:07:50 Z Alexa2001 Tropical Garden (IOI11_garden) C++17
69 / 100
 231 ms 39256 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

const int Nmax = 3e5 + 5;
using namespace std;

int n, m;
int Ans[Nmax], go[Nmax];
vector<int> v[Nmax], edge[Nmax], W[Nmax];

bool on_cycle[Nmax], used[Nmax], active[Nmax];
int pos_cycle[Nmax], CycleNr;

void dfs_down(int node, int level, int where) /// where = unde ar fi la momentul 0
{
    if(active[node])
        W[where].push_back(level);

    for(auto it : edge[node])
        dfs_down(it, level+1, (where - 1 + CycleNr) % CycleNr );
}

void precalc(int node)
{
    memset(used, 0, sizeof(used));
    memset(on_cycle, 0, sizeof(on_cycle));
    memset(pos_cycle, 0, sizeof(pos_cycle));

    int i;
    for(i=0; i<2*m; ++i)
    {
        edge[i].clear();
        W[i].clear();
    }

    while(!used[node]) used[node] = 1, node = go[node];

    /// node e pe ciclu si devine pos 0

    CycleNr = 0;
    while(!on_cycle[node])
    {
        pos_cycle[node] = CycleNr ++;
        on_cycle[node] = 1;
        node = go[node];
    }

    for(i=0; i<2*m; ++i)
        if(!on_cycle[i]) edge[go[i]].push_back(i);

    for(i=0; i<2*m; ++i)
        if(on_cycle[i]) dfs_down(i, 0, pos_cycle[i]);

    for(i=0; i<CycleNr; ++i) sort(W[i].begin(), W[i].end());
}

int cate(vector<int> &v, int x)
{
    int st = 0, dr = v.size() - 1, mid;
    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(v[mid] <= x) st = mid+1;
            else dr = mid-1;
    }
    return st;
}

void dfs_down2(int node, vector<int> &v, int level = 0)
{
    v[level] ++;
    for(auto it : edge[node])
        dfs_down2(it, v, level + 1);
}

void solve(int Q, int q[], int ans[], int Node)
{
    precalc(Node);

    int step;
    if(on_cycle[Node])
    {
        for(step = 0; step < Q; ++step)
        {
            int group = (pos_cycle[Node] - q[step] % CycleNr + CycleNr) % CycleNr;
            assert(group >= 0 && group < CycleNr);
            ans[step] += cate(W[group], q[step]); /// cate in group sunt <= q[i]
        }
        return;
    }

    ///

    vector<int> levels;
    levels.resize(Nmax);
    dfs_down2(Node, levels);

    for(step = 0; step < Q; ++step)
        if(q[step] < Nmax - 2) ans[step] += levels[q[step]];
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i;
    n = N; m = M;

    for(i=0; i<m; ++i)
    {
        int x, y;
        x = R[i][0];
        y = R[i][1];

        v[x].push_back(2*i); /// x->y
        v[y].push_back(2*i+1); /// y->x
    }

    set<int> S;

    for(i=0; i<m; ++i)
    {
        int x, y;
        x = R[i][0];
        y = R[i][1];

        if(v[y].size() >= 2 && v[y][0] == 2*i+1) go[2*i] = v[y][1];
            else go[2*i] = v[y][0];

        if(v[x].size() >= 2 && v[x][0] == 2*i) go[2*i+1] = v[x][1];
            else go[2*i+1] = v[x][0];

        if(y == P) S.insert(go[2*i]);
        if(x == P) S.insert(go[2*i+1]);

        if(v[x][0] == 2*i) active[2*i] = 1;
        if(v[y][0] == 2*i+1) active[2*i+1] = 1;
    }

    assert(S.size() <= 2);

    for(auto it : S)
        solve(Q, G, Ans, it);

    for(i=0; i<Q; ++i) answer(Ans[i]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23416 KB Output is correct
2 Correct 24 ms 23344 KB Output is correct
3 Correct 25 ms 23448 KB Output is correct
4 Correct 24 ms 23236 KB Output is correct
5 Correct 24 ms 24492 KB Output is correct
6 Correct 25 ms 23516 KB Output is correct
7 Correct 24 ms 23256 KB Output is correct
8 Correct 24 ms 23392 KB Output is correct
9 Correct 28 ms 23784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23416 KB Output is correct
2 Correct 24 ms 23344 KB Output is correct
3 Correct 25 ms 23448 KB Output is correct
4 Correct 24 ms 23236 KB Output is correct
5 Correct 24 ms 24492 KB Output is correct
6 Correct 25 ms 23516 KB Output is correct
7 Correct 24 ms 23256 KB Output is correct
8 Correct 24 ms 23392 KB Output is correct
9 Correct 28 ms 23784 KB Output is correct
10 Correct 24 ms 23272 KB Output is correct
11 Correct 39 ms 25844 KB Output is correct
12 Correct 64 ms 28100 KB Output is correct
13 Correct 68 ms 31068 KB Output is correct
14 Correct 196 ms 38388 KB Output is correct
15 Correct 227 ms 39256 KB Output is correct
16 Correct 198 ms 35384 KB Output is correct
17 Correct 225 ms 35420 KB Output is correct
18 Correct 76 ms 29172 KB Output is correct
19 Correct 176 ms 38320 KB Output is correct
20 Correct 224 ms 39192 KB Output is correct
21 Correct 231 ms 36752 KB Output is correct
22 Correct 192 ms 34724 KB Output is correct
23 Correct 200 ms 39148 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23416 KB Output is correct
2 Correct 24 ms 23344 KB Output is correct
3 Correct 25 ms 23448 KB Output is correct
4 Correct 24 ms 23236 KB Output is correct
5 Correct 24 ms 24492 KB Output is correct
6 Correct 25 ms 23516 KB Output is correct
7 Correct 24 ms 23256 KB Output is correct
8 Correct 24 ms 23392 KB Output is correct
9 Correct 28 ms 23784 KB Output is correct
10 Correct 24 ms 23272 KB Output is correct
11 Correct 39 ms 25844 KB Output is correct
12 Correct 64 ms 28100 KB Output is correct
13 Correct 68 ms 31068 KB Output is correct
14 Correct 196 ms 38388 KB Output is correct
15 Correct 227 ms 39256 KB Output is correct
16 Correct 198 ms 35384 KB Output is correct
17 Correct 225 ms 35420 KB Output is correct
18 Correct 76 ms 29172 KB Output is correct
19 Correct 176 ms 38320 KB Output is correct
20 Correct 224 ms 39192 KB Output is correct
21 Correct 231 ms 36752 KB Output is correct
22 Correct 192 ms 34724 KB Output is correct
23 Correct 200 ms 39148 KB Output is correct
24 Correct 24 ms 23260 KB Output is correct
25 Correct 41 ms 25872 KB Output is correct
26 Correct 72 ms 28208 KB Output is correct
27 Correct 71 ms 30840 KB Output is correct
28 Correct 188 ms 37672 KB Output is correct
29 Correct 227 ms 38812 KB Output is correct
30 Correct 197 ms 35384 KB Output is correct
31 Correct 229 ms 35504 KB Output is correct
32 Incorrect 81 ms 29520 KB Output isn't correct
33 Halted 0 ms 0 KB -