oj.uz

Submission #797228

# Submission time Handle Problem Language Result Execution time Memory
797228 2023-07-29T08:08:51 Z Khizri Tropical Garden (IOI11_garden) C++17
100 / 100
 2292 ms 36812 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=4e5+5;
int n,m,fin,k,best[mxn][3],go[mxn],color[mxn],color2[mxn],dis[mxn],dis2[mxn],sz=-1,sz2=-1;
vector<int>vt[mxn];
void dfs(int u,int dep){
    color[u]=1;
    dis[u]=dep;
    for(int v:vt[u]){
        if(!color[v]){
            dfs(v,dep+1);
        }
        else if(color[v]==1&&v==fin){
            sz=dep+1;
        }
    }
    color[u]=2;
}
void dfs2(int u,int dep){
    color2[u]=1;
    dis2[u]=dep;
    for(int v:vt[u]){
        if(!color2[v]){
            dfs2(v,dep+1);
        }
        else if(color2[v]==1&&v==fin+n){
            sz2=dep+1;
        }
    }
    color2[u]=2;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N,m=M,fin=P+1;
    for(int i=0;i<m;i++){
        int u=R[i][0]+1,v=R[i][1]+1;
        if(!best[u][0]){
            best[u][0]=v;
        }
        else if(!best[u][1]){
            best[u][1]=v;
        }
        if(!best[v][0]){
            best[v][0]=u;
        }
        else if(!best[v][1]){
            best[v][1]=u;
        }
    }
    for(int i=1;i<=n;i++){
        if(!best[i][1]){
            best[i][1]=best[i][0];
        }
    }
    for(int u=1;u<=n;u++){
        int x=best[u][0],y=best[u][1];
        if(best[x][0]==u){
            go[u]=x+n;
        }
        else{
            go[u]=x;
        }
        if(best[y][0]==u){
            go[u+n]=y+n;
        }
        else{
            go[u+n]=y;
        }
    }
    for(int i=1;i<=2*n;i++){
        vt[go[i]].pb(i);
    }
    for(int i=1;i<=2*n;i++){
        dis[i]=1e9+7;
        dis2[i]=1e9+7;
    }
    dfs(fin,0);
    dfs2(fin+n,0);
    for(int id=0;id<Q;id++){
        k=G[id];
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dis[i]==k||dis2[i]==k){
                ans++;
            }
            else{
                int x=k-dis[i],y=k-dis2[i];
                if(x>0&&sz>0&&x%sz==0){
                    ans++;
                }
                else if(y>0&&sz2>0&&y%sz2==0){
                    ans++;
                }
            }
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 5 ms 9688 KB Output is correct
11 Correct 13 ms 11732 KB Output is correct
12 Correct 18 ms 13032 KB Output is correct
13 Correct 34 ms 28000 KB Output is correct
14 Correct 51 ms 21544 KB Output is correct
15 Correct 63 ms 22476 KB Output is correct
16 Correct 44 ms 18288 KB Output is correct
17 Correct 44 ms 17528 KB Output is correct
18 Correct 18 ms 13080 KB Output is correct
19 Correct 62 ms 22308 KB Output is correct
20 Correct 65 ms 22452 KB Output is correct
21 Correct 45 ms 18128 KB Output is correct
22 Correct 50 ms 17512 KB Output is correct
23 Correct 52 ms 22352 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 5 ms 9688 KB Output is correct
11 Correct 13 ms 11732 KB Output is correct
12 Correct 18 ms 13032 KB Output is correct
13 Correct 34 ms 28000 KB Output is correct
14 Correct 51 ms 21544 KB Output is correct
15 Correct 63 ms 22476 KB Output is correct
16 Correct 44 ms 18288 KB Output is correct
17 Correct 44 ms 17528 KB Output is correct
18 Correct 18 ms 13080 KB Output is correct
19 Correct 62 ms 22308 KB Output is correct
20 Correct 65 ms 22452 KB Output is correct
21 Correct 45 ms 18128 KB Output is correct
22 Correct 50 ms 17512 KB Output is correct
23 Correct 52 ms 22352 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 91 ms 11808 KB Output is correct
26 Correct 126 ms 13168 KB Output is correct
27 Correct 2041 ms 28064 KB Output is correct
28 Correct 863 ms 22264 KB Output is correct
29 Correct 2283 ms 22496 KB Output is correct
30 Correct 1279 ms 18484 KB Output is correct
31 Correct 1246 ms 17568 KB Output is correct
32 Correct 145 ms 13644 KB Output is correct
33 Correct 888 ms 23724 KB Output is correct
34 Correct 2292 ms 24248 KB Output is correct
35 Correct 1371 ms 20000 KB Output is correct
36 Correct 1246 ms 19148 KB Output is correct
37 Correct 669 ms 24212 KB Output is correct
38 Correct 1770 ms 36812 KB Output is correct