Submission #229682

#	Time	Username	Problem	Language	Result	Execution time	Memory
229682		achibasadzishvili	Tropical Garden (IOI11_garden)	C++14	69 / 100	5074 ms	36856 KiB

garden

#include<bits/stdc++.h>
#include "gardenlib.h"
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,m,p,len[300005],o,raod,fix[300005],cik[300005],k,ye;
vector<ll>t[300005],rev[300005];
ll v[300005];
void dfs(ll x,ll dep,ll e,ll hav,ll z){
    if(fix[x])return;
    if(cik[x])hav = 1,z = len[cik[x]];
    if(dep == e || (hav && dep <= e && ((e - dep) % z) == 0))
        raod += (x <= n);
    fix[x] = 1;
    for(int i=0; i<rev[x].size(); i++)
        dfs(rev[x][i] , dep + 1 , e , hav , z);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n=N;
    m=M;
    p=P;
    p++;
    
    for(int i=1; i<=m; i++){
        ll x,y;
        x=R[i-1][0];
        y=R[i-1][1];
        x++;
        y++;
        if((int)t[x].size() < 2)t[x].pb(y);
        if((int)t[y].size() < 2)t[y].pb(x);
    }
    
    for(int x=1; x<=n; x++){
        v[x] = t[x][0];
        if(t[t[x][0]][0] == x){
            v[x] = t[x][0] + n;
        }
        if(t[x].size() == 1){
            v[x + n] = v[x];
            continue;
        }
        v[x + n] = t[x][1];
        if(t[t[x][1]][0] == x)v[x + n] = t[x][1] + n;
    }
    for(int i=1; i<=2 * n; i++){
        rev[v[i]].pb(i);
    }
    
    for(int i=1; i<=2*n; i++){
        ll st = i,pu = i,oof=0;
        while(1){
            if(fix[st] == i){
                pu = st;
                break;
            }
            if(fix[st] && fix[st] != i){
                oof = 1;
                break;
            }
            fix[st] = i;
            st = v[st];
        }
        if(oof)continue;
        st = pu;
        ll o = 0;
        while(!o || st != pu){
            len[i]++;
           // cout << st << " ";
            o = 1;
            cik[st] = i;
            st = v[st];
        }
        //cout << '\n';
    }
    int q = Q,in=0;
    
    while(q--){
        for(int i=1; i<=2 * n; i++)
            fix[i] = 0;
        k = G[in++];
        raod = 0;
        ye = 0;
        dfs(p , 0 , k , 0 , 0);
        for(int i=1; i<=2 * n; i++)
            fix[i] = 0;
        dfs(p + n , 0 , k , 0 , 0);
        answer(raod);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int, int, int)':
garden.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~

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