Submission #30559

#	Time	Username	Problem	Language	Result	Execution time	Memory
30559		top34051	Tropical Garden (IOI11_garden)	C++14	100 / 100	3151 ms	40932 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

#define maxn 150005

int p;
int sz0,sz1;
int from[maxn*2];
int vis[maxn*2];
int len[maxn*2][2];
vector<int> mn[maxn];
vector<int> re[maxn*2];
stack<int> st;

void dfs(int x,int last) {
    int t,cnt,ok0,ok1;
    if(vis[x]==1) {
//        printf("cycle ");
        cnt = ok0 = ok1 = 0;
        while(!st.empty()) {
            t = st.top(); st.pop();
//            printf("%d ",t);
            cnt++;
            if(t==p*2) ok0 = 1;
            if(t==p*2+1) ok1 = 1;
            if(t==x) break;
        }
        if(ok0) sz0 = cnt;
        if(ok1) sz1 = cnt;
//        printf("\n");
        return ;
    }
    vis[x] = 1;
    st.push(x);
    if(vis[from[x]]<=1) dfs(from[x],x);
    vis[x] = 2;
    if(!st.empty()) st.pop();
}

void dfs2(int x,int now) {
    int i,y;
    for(i=0;i<re[x].size();i++) {
        y = re[x][i];
        if(len[y][now]==-1) {
            len[y][now] = len[x][now] + 1;
            dfs2(y,now);
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int i,x,y,res;
    p = P;
    for(i=0;i<M;i++) {
        x = R[i][0]; y = R[i][1];
        if(mn[x].size()<2) mn[x].push_back(y);
        if(mn[y].size()<2) mn[y].push_back(x);
    }
    for(x=0;x<N;x++) if(mn[x].size()<2) mn[x].push_back(mn[x][0]);
    for(x=0;x<N;x++) {
        y = mn[x][1];
        if(mn[y][0]==x) from[x*2] = y*2;
        else from[x*2] = y*2+1;
        y = mn[x][0];
        if(mn[y][0]==x) from[x*2+1] = y*2;
        else from[x*2+1] = y*2+1;
//        printf("edge %d(%d) => %d(%d)\n",x,0,from[x*2]/2,from[x*2]%2);
//        printf("edge %d(%d) => %d(%d)\n",x,1,from[x*2+1]/2,from[x*2+1]%2);
    }
    for(x=0;x<2*N;x++) re[from[x]].push_back(x);
    for(x=0;x<2*N;x++) if(!vis[x]) dfs(x,-1);
    for(x=0;x<2*N;x++) len[x][0] = len[x][1] = -1;
    len[p*2][0] = 0;
    dfs2(p*2,0);
    len[p*2+1][1] = 0;
    dfs2(p*2+1,1);
//    printf("sz0 = %d sz1 = %d\n",sz0,sz1);
//    for(x=0;x<2*N;x++) printf("len %d 0 = %d   len %d 1 = %d\n",x,len[x][0],x,len[x][1]);
    for(i=0;i<Q;i++) {
        res = 0;
        for(x=1;x<2*N;x+=2) {
            if(len[x][0]!=-1 && G[i]==len[x][0]) res++;
            else if(len[x][1]!=-1 && G[i]==len[x][1]) res++;
            else if(sz0 && len[x][0]!=-1 && G[i]>=len[x][0] && (G[i]-len[x][0])%sz0==0) res++;
            else if(sz1 && len[x][1]!=-1 && G[i]>=len[x][1] && (G[i]-len[x][1])%sz1==0) res++;
        }
        answer(res);
    }
}

Compilation message (stderr)

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

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