oj.uz

Submission #851708

# Submission time Handle Problem Language Result Execution time Memory
851708 2023-09-20T12:18:48 Z 12345678 Tropical Garden (IOI11_garden) C++17
0 / 100
 3 ms 10840 KB 
#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]=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 ((G[i]-ds[j])%c==0&&ds[j]<=G[i]) cnt++;
            if ((G[i]-dss[j])%cs==0&&dss[j]<=G[i]) cnt++;
        }
        answer(cnt);
    }
}
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
4
3 1 5 9
1 2 2 2
*/

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -