Submission #494043

#	Time	Username	Problem	Language	Result	Execution time	Memory
494043		Ozy	Tropical Garden (IOI11_garden)	C++17	100 / 100	2637 ms	44460 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31