oj.uz

Submission #797226

# Submission time Handle Problem Language Result Execution time Memory
797226 2023-07-29T08:07:45 Z Khizri Tropical Garden (IOI11_garden) C++17
69 / 100
 2292 ms 29312 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(i==fin) continue;
            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++;
                }
            }
        }
        if((sz>0&&k%sz==0)||(sz2>0&&k%sz2==0)) ans++;
        answer(ans);
    }
}
/*
g++ garden.cpp grader.cpp ; .\a.exe
5 5 2
1 0
1 2
3 2
1 3
4 2
1
1

6 6 0
1 2
0 1
0 3
3 4
4 5
1 6
1 3
*/

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 9772 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 6 ms 9792 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 9772 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 6 ms 9792 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 11 ms 11732 KB Output is correct
12 Correct 18 ms 13012 KB Output is correct
13 Correct 37 ms 27984 KB Output is correct
14 Correct 53 ms 21540 KB Output is correct
15 Correct 74 ms 22428 KB Output is correct
16 Correct 48 ms 18228 KB Output is correct
17 Correct 44 ms 17464 KB Output is correct
18 Correct 18 ms 13072 KB Output is correct
19 Correct 54 ms 22136 KB Output is correct
20 Correct 72 ms 22472 KB Output is correct
21 Correct 52 ms 18076 KB Output is correct
22 Correct 43 ms 17544 KB Output is correct
23 Correct 55 ms 22428 KB Output is correct

Subtask #3
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 9772 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 6 ms 9792 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 11 ms 11732 KB Output is correct
12 Correct 18 ms 13012 KB Output is correct
13 Correct 37 ms 27984 KB Output is correct
14 Correct 53 ms 21540 KB Output is correct
15 Correct 74 ms 22428 KB Output is correct
16 Correct 48 ms 18228 KB Output is correct
17 Correct 44 ms 17464 KB Output is correct
18 Correct 18 ms 13072 KB Output is correct
19 Correct 54 ms 22136 KB Output is correct
20 Correct 72 ms 22472 KB Output is correct
21 Correct 52 ms 18076 KB Output is correct
22 Correct 43 ms 17544 KB Output is correct
23 Correct 55 ms 22428 KB Output is correct
24 Correct 8 ms 9684 KB Output is correct
25 Correct 102 ms 11988 KB Output is correct
26 Correct 149 ms 13652 KB Output is correct
27 Correct 2050 ms 29312 KB Output is correct
28 Correct 905 ms 23956 KB Output is correct
29 Correct 2292 ms 24268 KB Output is correct
30 Correct 1288 ms 20176 KB Output is correct
31 Incorrect 1251 ms 19140 KB Output isn't correct
32 Halted 0 ms 0 KB -