oj.uz

Submission #494043

# Submission time Handle Problem Language Result Execution time Memory
494043 2021-12-14T02:07:42 Z Ozy Tropical Garden (IOI11_garden) C++17
100 / 100
 2637 ms 44460 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 150000

lli n,m,p,a,b,ini,res;
lli cont[MAX+2],uno[MAX+2];
vector<lli> hijos[MAX*3];

lli dist[2][MAX*3];
lli tam[2],visitados[2][MAX*3],k;
stack<lli> pila;
vector<lli> ciclo;

void asigna(lli x, lli y) {

    if (cont[x] == 0) {

        if (cont[y] == 0 && uno[y] > 1) hijos[y+n].push_back(x);
        else hijos[y].push_back(x);

    }
    else if (cont[x] == 1) {

        if (cont[y] == 0 && uno[y] > 1) hijos[y+n].push_back(x+n);
        else hijos[y].push_back(x+n);

    }
    else return;

}

void dfs(lli pos, lli dis, lli id) {

    visitados[id][pos] = 1;
    dist[id][pos] = dis;

    for (auto h : hijos[pos]) {

        if (visitados[id][h] == 1) tam[id] = dis+1;
        else dfs(h,dis+1,id);

    }

}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

    n = N;
    m = M;
    p = P;

    rep(i,0,m-1) {
        a = R[i][0];
        b = R[i][1];
        uno[a]++;
        uno[b]++;
    }

    rep(i,0,m-1) {
        a = R[i][0];
        b = R[i][1];

        asigna(a,b);
        asigna(b,a);

        cont[a]++;
        cont[b]++;
    }

    dfs(p,0,0);
    dfs(p+n,0,1);

    rep(q,0,Q-1) {

        res = 0;
        k = G[q];

        rep(i,0,n-1) {

            rep(j,0,1) {

                //debugsl(j);
                //debugsl(i);
                //debug(dist[j][i]);

                if (visitados[j][i] == 0) continue;

                a = k - dist[j][i];
                if (a == 0) {res++; break;}
                else if (a > 0) {
                    if (tam[j] > 0 && (a%tam[j]) == 0) {res++; break;}
                }

            }

        }

        answer(res);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11084 KB Output is correct
2 Correct 6 ms 11008 KB Output is correct
3 Correct 5 ms 11084 KB Output is correct
4 Correct 6 ms 10876 KB Output is correct
5 Correct 8 ms 10828 KB Output is correct
6 Correct 7 ms 11084 KB Output is correct
7 Correct 8 ms 10880 KB Output is correct
8 Correct 7 ms 11012 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11084 KB Output is correct
2 Correct 6 ms 11008 KB Output is correct
3 Correct 5 ms 11084 KB Output is correct
4 Correct 6 ms 10876 KB Output is correct
5 Correct 8 ms 10828 KB Output is correct
6 Correct 7 ms 11084 KB Output is correct
7 Correct 8 ms 10880 KB Output is correct
8 Correct 7 ms 11012 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct
10 Correct 7 ms 10812 KB Output is correct
11 Correct 12 ms 13076 KB Output is correct
12 Correct 22 ms 14924 KB Output is correct
13 Correct 43 ms 35220 KB Output is correct
14 Correct 56 ms 25564 KB Output is correct
15 Correct 89 ms 29424 KB Output is correct
16 Correct 67 ms 21724 KB Output is correct
17 Correct 65 ms 22704 KB Output is correct
18 Correct 22 ms 15024 KB Output is correct
19 Correct 61 ms 27540 KB Output is correct
20 Correct 81 ms 29364 KB Output is correct
21 Correct 64 ms 21524 KB Output is correct
22 Correct 64 ms 22660 KB Output is correct
23 Correct 63 ms 25844 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11084 KB Output is correct
2 Correct 6 ms 11008 KB Output is correct
3 Correct 5 ms 11084 KB Output is correct
4 Correct 6 ms 10876 KB Output is correct
5 Correct 8 ms 10828 KB Output is correct
6 Correct 7 ms 11084 KB Output is correct
7 Correct 8 ms 10880 KB Output is correct
8 Correct 7 ms 11012 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct
10 Correct 7 ms 10812 KB Output is correct
11 Correct 12 ms 13076 KB Output is correct
12 Correct 22 ms 14924 KB Output is correct
13 Correct 43 ms 35220 KB Output is correct
14 Correct 56 ms 25564 KB Output is correct
15 Correct 89 ms 29424 KB Output is correct
16 Correct 67 ms 21724 KB Output is correct
17 Correct 65 ms 22704 KB Output is correct
18 Correct 22 ms 15024 KB Output is correct
19 Correct 61 ms 27540 KB Output is correct
20 Correct 81 ms 29364 KB Output is correct
21 Correct 64 ms 21524 KB Output is correct
22 Correct 64 ms 22660 KB Output is correct
23 Correct 63 ms 25844 KB Output is correct
24 Correct 7 ms 10888 KB Output is correct
25 Correct 190 ms 13080 KB Output is correct
26 Correct 270 ms 15124 KB Output is correct
27 Correct 2280 ms 35248 KB Output is correct
28 Correct 1399 ms 28876 KB Output is correct
29 Correct 2551 ms 29428 KB Output is correct
30 Correct 1695 ms 22024 KB Output is correct
31 Correct 1447 ms 22728 KB Output is correct
32 Correct 297 ms 15172 KB Output is correct
33 Correct 1392 ms 26632 KB Output is correct
34 Correct 2637 ms 29460 KB Output is correct
35 Correct 1699 ms 22160 KB Output is correct
36 Correct 1467 ms 22720 KB Output is correct
37 Correct 1221 ms 25948 KB Output is correct
38 Correct 2194 ms 44460 KB Output is correct