제출 #851705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851705		12345678	Tropical Garden (IOI11_garden)	C++17	0 / 100	2 ms	10840 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;
        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;
        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]=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++) cout<<i<<' '<<v[i]<<' '<<vs[i]<<'\n';
    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);
    }/*
    for (int i=0; i<n; i++)
    {
        cout<<i<<": ";
        for (auto x:d[i]) cout<<x<<' ';
        cout<<'\n';
        cout<<i+n<<": ";
        for (auto x:d[i+n]) cout<<x<<' ';
        cout<<'\n';
    }*/
    dfs(p, 0);
    dfs2(p+n, 0);/*
    cout<<"sz "<<c<<' '<<cs<<'\n';
    for (int i=0; i<n; i++) cout<<ds[i]<<' ';
    cout<<'\n';
    for (int i=0; i<n; i++) cout<<dss[i]<<' ';
    cout<<'\n';*/
    for (int i=0; i<Q; i++)
    {
        int cnt(0);
        for (int j=0; j<n; j++)
        {
            if (ds[j]==G[i]) cnt++;
            else if (G[i]-ds[i]>0&&(ds[i]-G[i])%c==0) cnt++;
            if (dss[j]==G[i]) cnt++;
            else if (G[i]-dss[i]>0&&(dss[i]-G[i])%cs==0) cnt++;
        }
        answer(cnt);
    }
}

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