Submission #851738

#	Time	Username	Problem	Language	Result	Execution time	Memory
851738		12345678	Tropical Garden (IOI11_garden)	C++17	49 / 100	30 ms	27220 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"

using namespace std;

const int nx=150005;
int ds[nx], dss[nx], c=INT_MAX, cs=INT_MAX, ans, n, p, v[nx], vs[nx];
bool vs1[2*nx], vs2[2*nx];
vector<int> d[2*nx];

void dfs(int u, int s)
{
    if (vs1[u]) return;
    ds[u]=s;
    vs1[u]=1;
    for (auto v:d[u])
    {
        if (v==p) c=s+1;
        else dfs(v, s+1);
    } 
}

void dfs2(int u, int s)
{
    if (vs2[u]) return;
    vs2[u]=1;
    dss[u]=s;
    for (auto v:d[u])
    {
        if (v==p+n) cs=s+1;
        else dfs2(v, s+1);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for (int i=0; i<N; i++) ds[i]=dss[i]=INT_MAX, vs[i]=v[i]=-1;
    n=N; p=P;
    for (int i=0; i<M; i++)
    {
        if (v[R[i][0]]==-1) v[R[i][0]]=R[i][1];
        else if (vs[R[i][0]]==-1) vs[R[i][0]]=R[i][1];
        if (v[R[i][1]]==-1) v[R[i][1]]=R[i][0];
        else if (vs[R[i][1]]==-1) vs[R[i][1]]=R[i][0];
    }
    for (int i=0; i<N; i++) if (vs[i]==-1) vs[i]=v[i];
    for (int i=0; i<N; i++)
    {
        if (v[v[i]]==i) d[v[i]+n].push_back(i);
        else d[v[i]].push_back(i);
        if (v[vs[i]]==i) d[vs[i]+n].push_back(i+n);
        else d[vs[i]].push_back(i+n);
    }
    dfs(p, 0);
    dfs2(p+n, 0);
    for (int i=0; i<Q; i++)
    {
        int cnt(0);
        for (int j=0; j<n; j++)
        {
            if (((G[i]-ds[j])%c==0&&ds[j]<=G[i])||((G[i]-dss[j])%cs==0&&dss[j]<=G[i])) cnt++;
        }
        answer(cnt);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31