oj.uz

Submission #790439

# Submission time Handle Problem Language Result Execution time Memory
790439 2023-07-22T16:32:26 Z kilikuma Tropical Garden (IOI11_garden) C++14
100 / 100
 2421 ms 25684 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=400100;
typedef long long ll;

vector<int> listeCourante[N];
int pass[N],areteCourante[N],d0[N],d1[N];
void answer(int X);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{

    for(int i=0;i<M;i++)
        areteCourante[R[i][0]]++,areteCourante[R[i][1]]++;
    for(int i=0;i<M;i++)
    {
        int u0=2*R[i][0],v0=2*R[i][1];
        if(pass[R[i][0]]<=1)
        {
            if(!pass[R[i][1]]){
                if(areteCourante[R[i][0]]==1){
                    listeCourante[v0+1].push_back(u0);
                    listeCourante[v0+1].push_back(u0+1);
                }else
                    listeCourante[v0+1].push_back(u0+pass[R[i][0]]);
            }else
            {

                if(areteCourante[R[i][0]]==1){
                    listeCourante[v0].push_back(u0);
                    listeCourante[v0].push_back(u0+1);
                }else
                    listeCourante[v0].push_back(u0+pass[R[i][0]]);
            }

        }
        if(pass[R[i][1]]<=1)
        {
            if(!pass[R[i][0]]){
                if(areteCourante[R[i][1]]==1){
                    listeCourante[u0+1].push_back(v0);
                    listeCourante[u0+1].push_back(v0+1);
                }else
                    listeCourante[u0+1].push_back(v0+pass[R[i][1]]);
            }else
            {
                if(areteCourante[R[i][1]]==1){
                    listeCourante[u0].push_back(v0);
                    listeCourante[u0].push_back(v0+1);
                }else
                    listeCourante[u0].push_back(v0+pass[R[i][1]]);
            }
        }
        pass[R[i][0]]++;
        pass[R[i][1]]++;
    }
    queue<int> f;
    f.push(2*P);
    d0[2*P]=1;
    int c0=-1;
    while(!f.empty())
    {
        int u=f.front();
        f.pop();
        for(int v:listeCourante[u])
        {
            if(!d0[v])
            {
                d0[v]= d0[u]+1;
                f.push(v);
            }else
            {
                c0=d0[u];
            }
        }
    }
    f.push(2*P+1);
    d1[2*P+1]=1;
    int c1=-1;
    while(!f.empty())
    {
        int u=f.front();
        f.pop();
        for(int v:listeCourante[u])
        {
            if(!d1[v])
            {

                d1[v]= d1[u]+1;
                f.push(v);
            }else
            {
                c1=d1[u];
            }
        }
    }

    for(int i=0;i<=2*N;i++){
        d0[i]--,d1[i]--;
    }
    for(int j=0;j<Q;j++)
    {
        int rs=0;
        for(int i=0;i<N;i++)
        {
            if(G[j]==d0[2*i] || G[j]==d1[2*i]){
                rs++;
            }
            else if(d0[2*i]!=-1 && c0!=-1 && G[j]>=d0[2*i] &&(G[j]-d0[2*i])%c0==0){
                rs++;
            }
            else if(d1[2*i]!=-1 && c1!=-1 && G[j]>=d1[2*i] && (G[j]-d1[2*i])%c1==0){
                rs++;
            }
        }
        answer(rs);
    }

}

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9812 KB Output is correct
2 Correct 4 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9816 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 9 ms 11348 KB Output is correct
12 Correct 15 ms 12284 KB Output is correct
13 Correct 28 ms 17656 KB Output is correct
14 Correct 40 ms 18460 KB Output is correct
15 Correct 58 ms 18764 KB Output is correct
16 Correct 56 ms 16228 KB Output is correct
17 Correct 36 ms 15532 KB Output is correct
18 Correct 24 ms 12388 KB Output is correct
19 Correct 45 ms 18512 KB Output is correct
20 Correct 55 ms 18764 KB Output is correct
21 Correct 38 ms 16316 KB Output is correct
22 Correct 41 ms 15480 KB Output is correct
23 Correct 55 ms 19388 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9812 KB Output is correct
2 Correct 4 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9816 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 9 ms 11348 KB Output is correct
12 Correct 15 ms 12284 KB Output is correct
13 Correct 28 ms 17656 KB Output is correct
14 Correct 40 ms 18460 KB Output is correct
15 Correct 58 ms 18764 KB Output is correct
16 Correct 56 ms 16228 KB Output is correct
17 Correct 36 ms 15532 KB Output is correct
18 Correct 24 ms 12388 KB Output is correct
19 Correct 45 ms 18512 KB Output is correct
20 Correct 55 ms 18764 KB Output is correct
21 Correct 38 ms 16316 KB Output is correct
22 Correct 41 ms 15480 KB Output is correct
23 Correct 55 ms 19388 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 118 ms 11392 KB Output is correct
26 Correct 165 ms 12996 KB Output is correct
27 Correct 2044 ms 18720 KB Output is correct
28 Correct 1085 ms 20272 KB Output is correct
29 Correct 2380 ms 20572 KB Output is correct
30 Correct 1300 ms 17872 KB Output is correct
31 Correct 1271 ms 17112 KB Output is correct
32 Correct 173 ms 13000 KB Output is correct
33 Correct 1087 ms 20244 KB Output is correct
34 Correct 2337 ms 20560 KB Output is correct
35 Correct 1371 ms 17876 KB Output is correct
36 Correct 1561 ms 17116 KB Output is correct
37 Correct 860 ms 21204 KB Output is correct
38 Correct 2421 ms 25684 KB Output is correct