oj.uz

Submission #784032

# Submission time Handle Problem Language Result Execution time Memory
784032 2023-07-15T15:04:54 Z gagik_2007 Tropical Garden (IOI11_garden) C++17
0 / 100
 5 ms 9812 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=400007;
ll n,m,k;
vector<int>g[N];
bool done[N];
bool in_cycle[2];
int clen=0;
int dist[N][2];
bool used[N][2];

void is_in_cycle(int c, int v, int par){
    for(int to:g[v]){
        if(to==c){
            if(c>=n)in_cycle[1]=true;
            else in_cycle[0]=true;
        }
        else if(to!=par){
            is_in_cycle(c,to,v);
        }
    }
}

void dfs(int v, int cur, int i, int c){
    used[v][i]=true;
    dist[v][i]=cur;
    for(int to:g[v]){
        if(!used[to][i]){
            dfs(to,(abs(to-v)==n?cur:cur+1),i,c);
        }
        else if(to==c){
            clen=cur+1;
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n=N;
    m=M;
    k=P;
    for(int i=0;i<m;i++){
        int v=R[i][0];
        int u=R[i][1];
        // cout<<v<<" "<<u<<endl;
        if(!done[v]||!done[v+n]){
            if(!done[v]){
                if(!done[u]){
                    g[u+n].push_back(v);
                }
                else{
                    g[u].push_back(v);
                }
            }
            else{
                if(!done[u]){
                    g[u+n].push_back(v+n);
                }
                else{
                    g[u].push_back(v+n);
                }
            }
        }
        if(!done[u]||!done[u+n]){
            if(!done[u]){
                if(!done[v]){
                    g[v+n].push_back(u);
                }
                else{
                    g[v].push_back(u);
                }
            }
            else{
                if(!done[v]){
                    g[v+n].push_back(u+n);
                }
                else{
                    g[v].push_back(u+n);
                }
            }
        }
        if(!done[v]||!done[v+n]){
            if(!done[v]){
                done[v]=true;
            }
            else{
                done[v+n]=true;
            }
        }
        if(!done[u]||!done[u+n]){
            if(!done[u]){
                done[u]=true;
            }
            else{
                done[u+n]=true;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(!done[i+n]){
            done[i+n]=true;
            g[i].push_back(i+n);
        }
    }
    for(int v=0;v<2*n;v++){
        // for(int to:g[v]){
        //     cout<<v<<" "<<to<<endl;
        // }
        dist[v][0]=dist[v][1]=MOD;
    }
    cout<<endl;
    is_in_cycle(k,k,k);
    is_in_cycle(k+n,k+n,k+n);
    dfs(k,0,0,k);
    dfs(k+n,0,1,k+n);
    // for(int v=0;v<2*n;v++){
    //     cout<<dist[v][0]<<" "<<dist[v][1]<<endl;
    // }
    for(int i=0;i<Q;i++){
        int cnt=0;
        for(int v=0;v<n;v++){
            if(in_cycle[0]){
                if(dist[v][0]<=G[i]&&dist[v][0]%clen==G[i]%clen)cnt++;
            }
            else if(dist[v][0]==G[i])cnt++;
            if(in_cycle[1]){
                if(dist[v][1]<=G[i]&&dist[v][1]%clen==G[i]%clen)cnt++;
            }
            else if(dist[v][1]==G[i])cnt++;
        }
        answer(cnt);
    }
}

Subtask #1
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 4 ms 9812 KB Output is correct
4 Incorrect 4 ms 9704 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 4 ms 9812 KB Output is correct
4 Incorrect 4 ms 9704 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 4 ms 9812 KB Output is correct
4 Incorrect 4 ms 9704 KB Output isn't correct
5 Halted 0 ms 0 KB -