Submission #30555

#	Time	Username	Problem	Language	Result	Execution time	Memory
30555		top34051	Tropical Garden (IOI11_garden)	C++14	0 / 100	12 ms	11148 KiB

garden

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

#define maxn 150005

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 = 0;
        while(!st.empty()) {
            t = st.top(); st.pop();
//            printf("%d ",t);
            cnt++;
            if(t==0) ok0 = 1;
            if(t==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;
    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;
    }
    for(x=0;x<2*N;x++) re[from[x]].push_back(x);
    for(x=0;x<N;x++) if(!vis[x*2]) dfs(x*2,-1);
    for(x=0;x<2*N;x++) len[x][0] = len[x][1] = -1;
    dfs2(0,0); dfs2(1,1);
    for(i=0;i<Q;i++) {
        res = 0;
        for(x=0;x<2*N;x++) if((len[x][0]!=-1 && G[i]>=len[x][0] && (G[i]-len[x][0])%sz0==0) || (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:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<re[x].size();i++) {
             ~^~~~~~~~~~~~~

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