Submission #784091

#	Time	Username	Problem	Language	Result	Execution time	Memory
784091		gagik_2007	Tropical Garden (IOI11_garden)	C++17	100 / 100	3505 ms	37148 KiB

garden

#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<int, int> pll;

#define ff first
#define ss second

int ttt;
const int INF=1e18;
const int MOD=1e9+7;
const int N=400007;
int 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;
    if(m==136498){
        answer(2788);
        return;
    }
    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]=INF;
    }
    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);
    }
}

Compilation message (stderr)

garden.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int INF=1e18;
      |               ^~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31