oj.uz

Submission #851743

# Submission time Handle Problem Language Result Execution time Memory
851743 2023-09-20T14:05:32 Z 12345678 Tropical Garden (IOI11_garden) C++17
49 / 100
 28 ms 26200 KB 
#include "garden.h"
#include "gardenlib.h"
#include "bits/stdc++.h"

using namespace std;

const int nx=150100;
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;
    vs1[u]=1; ds[u]=s;
    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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 3 ms 10840 KB Output is correct
11 Correct 8 ms 11868 KB Output is correct
12 Correct 17 ms 12124 KB Output is correct
13 Incorrect 28 ms 26200 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 3 ms 10840 KB Output is correct
11 Correct 8 ms 11868 KB Output is correct
12 Correct 17 ms 12124 KB Output is correct
13 Incorrect 28 ms 26200 KB Output isn't correct
14 Halted 0 ms 0 KB -