oj.uz

Submission #784072

# Submission time Handle Problem Language Result Execution time Memory
784072 2023-07-15T15:46:24 Z gagik_2007 Tropical Garden (IOI11_garden) C++17
49 / 100
 124 ms 31808 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=(abs(to-v)==n?cur: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;
    // }
    // cout<<"clen: "<<clen<<endl;
    for(int i=0;i<Q;i++){
        int cnt=0;
        for(int v=0;v<n;v++){
            int lcnt=cnt;
            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++;
            // if(cnt>lcnt)cout<<v<<endl;
            if(cnt-lcnt==2)cnt--;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9908 KB Output is correct
2 Correct 4 ms 9812 KB Output is correct
3 Correct 6 ms 9844 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9712 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9716 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 9684 KB Output is correct
11 Correct 13 ms 11768 KB Output is correct
12 Correct 20 ms 13108 KB Output is correct
13 Correct 46 ms 31808 KB Output is correct
14 Correct 47 ms 21640 KB Output is correct
15 Correct 94 ms 21844 KB Output is correct
16 Correct 70 ms 18376 KB Output is correct
17 Correct 48 ms 17000 KB Output is correct
18 Correct 17 ms 13048 KB Output is correct
19 Correct 71 ms 21636 KB Output is correct
20 Correct 124 ms 21812 KB Output is correct
21 Correct 78 ms 18240 KB Output is correct
22 Incorrect 49 ms 17052 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9908 KB Output is correct
2 Correct 4 ms 9812 KB Output is correct
3 Correct 6 ms 9844 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9712 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9716 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 9684 KB Output is correct
11 Correct 13 ms 11768 KB Output is correct
12 Correct 20 ms 13108 KB Output is correct
13 Correct 46 ms 31808 KB Output is correct
14 Correct 47 ms 21640 KB Output is correct
15 Correct 94 ms 21844 KB Output is correct
16 Correct 70 ms 18376 KB Output is correct
17 Correct 48 ms 17000 KB Output is correct
18 Correct 17 ms 13048 KB Output is correct
19 Correct 71 ms 21636 KB Output is correct
20 Correct 124 ms 21812 KB Output is correct
21 Correct 78 ms 18240 KB Output is correct
22 Incorrect 49 ms 17052 KB Output isn't correct
23 Halted 0 ms 0 KB -