답안 #95116 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95116	2019-01-27T12:23:40 Z	Alexa2001	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	271 ms	43552 KB

garden

#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)
{
    if(active[node]) 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

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23416 KB	Output is correct
2	Correct	24 ms	23388 KB	Output is correct
3	Correct	24 ms	23424 KB	Output is correct
4	Correct	23 ms	23292 KB	Output is correct
5	Correct	24 ms	24428 KB	Output is correct
6	Correct	26 ms	23436 KB	Output is correct
7	Correct	24 ms	23320 KB	Output is correct
8	Correct	24 ms	23336 KB	Output is correct
9	Correct	26 ms	23604 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23416 KB	Output is correct
2	Correct	24 ms	23388 KB	Output is correct
3	Correct	24 ms	23424 KB	Output is correct
4	Correct	23 ms	23292 KB	Output is correct
5	Correct	24 ms	24428 KB	Output is correct
6	Correct	26 ms	23436 KB	Output is correct
7	Correct	24 ms	23320 KB	Output is correct
8	Correct	24 ms	23336 KB	Output is correct
9	Correct	26 ms	23604 KB	Output is correct
10	Correct	23 ms	23316 KB	Output is correct
11	Correct	39 ms	25604 KB	Output is correct
12	Correct	70 ms	27592 KB	Output is correct
13	Correct	69 ms	30124 KB	Output is correct
14	Correct	182 ms	36968 KB	Output is correct
15	Correct	222 ms	37764 KB	Output is correct
16	Correct	216 ms	34632 KB	Output is correct
17	Correct	224 ms	34696 KB	Output is correct
18	Correct	77 ms	28860 KB	Output is correct
19	Correct	185 ms	36828 KB	Output is correct
20	Correct	221 ms	37780 KB	Output is correct
21	Correct	234 ms	35892 KB	Output is correct
22	Correct	193 ms	33520 KB	Output is correct
23	Correct	198 ms	38000 KB	Output is correct

Subtask #3
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	23416 KB	Output is correct
2	Correct	24 ms	23388 KB	Output is correct
3	Correct	24 ms	23424 KB	Output is correct
4	Correct	23 ms	23292 KB	Output is correct
5	Correct	24 ms	24428 KB	Output is correct
6	Correct	26 ms	23436 KB	Output is correct
7	Correct	24 ms	23320 KB	Output is correct
8	Correct	24 ms	23336 KB	Output is correct
9	Correct	26 ms	23604 KB	Output is correct
10	Correct	23 ms	23316 KB	Output is correct
11	Correct	39 ms	25604 KB	Output is correct
12	Correct	70 ms	27592 KB	Output is correct
13	Correct	69 ms	30124 KB	Output is correct
14	Correct	182 ms	36968 KB	Output is correct
15	Correct	222 ms	37764 KB	Output is correct
16	Correct	216 ms	34632 KB	Output is correct
17	Correct	224 ms	34696 KB	Output is correct
18	Correct	77 ms	28860 KB	Output is correct
19	Correct	185 ms	36828 KB	Output is correct
20	Correct	221 ms	37780 KB	Output is correct
21	Correct	234 ms	35892 KB	Output is correct
22	Correct	193 ms	33520 KB	Output is correct
23	Correct	198 ms	38000 KB	Output is correct
24	Correct	24 ms	23288 KB	Output is correct
25	Correct	39 ms	25564 KB	Output is correct
26	Correct	68 ms	27496 KB	Output is correct
27	Correct	70 ms	30104 KB	Output is correct
28	Correct	186 ms	36924 KB	Output is correct
29	Correct	225 ms	37908 KB	Output is correct
30	Correct	208 ms	34632 KB	Output is correct
31	Correct	222 ms	34744 KB	Output is correct
32	Correct	76 ms	28888 KB	Output is correct
33	Correct	271 ms	38020 KB	Output is correct
34	Correct	222 ms	38928 KB	Output is correct
35	Correct	239 ms	37004 KB	Output is correct
36	Correct	241 ms	35716 KB	Output is correct
37	Correct	200 ms	38980 KB	Output is correct
38	Correct	267 ms	43552 KB	Output is correct

답안 #95116

Compilation message

Subtask #1 49.0 / 49.0

Subtask #2 20.0 / 20.0

Subtask #3 31.0 / 31.0

Subtask #1
49.0 / 49.0

Subtask #2
20.0 / 20.0

Subtask #3
31.0 / 31.0