oj.uz

Submission #16488

# Submission time Handle Problem Language Result Execution time Memory
16488 2015-08-26T11:25:52 Z khsoo01 Tropical Garden (IOI11_garden) C++
0 / 100
 15 ms 14548 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define INF 0x7fffffff
using namespace std;
vector<int>cg[300005],cn[300005];
int n,m,p,ed[300005][2],cur,flag,vis[300005],cnt;
int dist[2][300005],cyc_len[2];
bool state,in_cyc[2];

void find_cyc(int idx) {
    if(vis[idx]==1) {
        if(!in_cyc[state] && idx!=cn[p][state]) return;
        in_cyc[state]=true;
        cyc_len[state]++;
    }
    if(vis[idx]==2) return;
    vis[idx]++;
    find_cyc(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0]);
    vis[idx]=0;
}

int find_dist(int idx) {
    if(cn[p][state]==idx) return dist[state][idx]=0;
    if(vis[idx]) return dist[state][idx];
    vis[idx]++;
    return dist[state][idx]=find_dist(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0])+1;
    vis[idx]=0;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i,j,tmp; n=N; m=M; p=P;
    for(i=0;i<m;i++) {
        ed[i][0]=R[i][0];
        ed[i][1]=R[i][1];
        ed[i+m][0]=R[i][1];
        ed[i+m][1]=R[i][0];
        cg[ed[i][0]].push_back(ed[i][1]);
        cn[ed[i][0]].push_back(i);
        cg[ed[i][1]].push_back(ed[i][0]);
        cn[ed[i][1]].push_back(i+m);
        dist[0][i]=-INF;
        dist[1][i]=-INF;
        dist[0][i+M]=-INF;
        dist[1][i+M]=-INF;
    }
    state=0;
    find_cyc(cn[p][0]);
    state=1;
    find_cyc(cn[p][1]);
    state=0;
    for(i=0;i<2*m;i++) {
        if(vis[i])continue;
        find_dist(i);
    }
    state=1;
    for(i=0;i<2*m;i++) {
        if(vis[i])continue;
        find_dist(i);
    }
    for(i=0;i<Q;i++) {
        cnt=0;
        for(j=0;j<n;j++) {
            tmp=cn[j][0];
            if(dist[0][tmp]==G[i]){
                cnt++; continue;
            }
            if(dist[1][tmp]==G[i]){
                cnt++; continue;
            }
            if(in_cyc[0] && dist[0][tmp]>=0 && dist[0][tmp]<G[i] && (G[i]-dist[0][tmp])%cyc_len[0]==0) {
                cnt++; continue;
            }
            if(in_cyc[1] && dist[1][tmp]>=0 && dist[1][tmp]<G[i] && (G[i]-dist[1][tmp])%cyc_len[1]==0) {
                cnt++; continue;
            }
        }
        answer(cnt);
    }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -