oj.uz

Submission #16481

# Submission time Handle Problem Language Result Execution time Memory
16481 2015-08-26T11:18:53 Z khsoo01 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 31288 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;
}

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;
    memset(vis,0,sizeof(vis));
    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
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 17 ms 15664 KB Output is correct
3 Correct 17 ms 15780 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15584 KB Output is correct
6 Correct 17 ms 15852 KB Output is correct
7 Correct 16 ms 15684 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 17 ms 15664 KB Output is correct
3 Correct 17 ms 15780 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15584 KB Output is correct
6 Correct 17 ms 15852 KB Output is correct
7 Correct 16 ms 15684 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16224 KB Output is correct
10 Correct 16 ms 15668 KB Output is correct
11 Correct 32 ms 17928 KB Output is correct
12 Correct 65 ms 20484 KB Output is correct
13 Correct 83 ms 29540 KB Output is correct
14 Correct 235 ms 29976 KB Output is correct
15 Correct 258 ms 30488 KB Output is correct
16 Correct 243 ms 27784 KB Output is correct
17 Correct 233 ms 27224 KB Output is correct
18 Correct 72 ms 20388 KB Output is correct
19 Correct 248 ms 30072 KB Output is correct
20 Correct 261 ms 30460 KB Output is correct
21 Correct 240 ms 27664 KB Output is correct
22 Correct 243 ms 26904 KB Output is correct
23 Correct 240 ms 31288 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15736 KB Output is correct
2 Correct 17 ms 15664 KB Output is correct
3 Correct 17 ms 15780 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15584 KB Output is correct
6 Correct 17 ms 15852 KB Output is correct
7 Correct 16 ms 15684 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16224 KB Output is correct
10 Correct 16 ms 15668 KB Output is correct
11 Correct 32 ms 17928 KB Output is correct
12 Correct 65 ms 20484 KB Output is correct
13 Correct 83 ms 29540 KB Output is correct
14 Correct 235 ms 29976 KB Output is correct
15 Correct 258 ms 30488 KB Output is correct
16 Correct 243 ms 27784 KB Output is correct
17 Correct 233 ms 27224 KB Output is correct
18 Correct 72 ms 20388 KB Output is correct
19 Correct 248 ms 30072 KB Output is correct
20 Correct 261 ms 30460 KB Output is correct
21 Correct 240 ms 27664 KB Output is correct
22 Correct 243 ms 26904 KB Output is correct
23 Correct 240 ms 31288 KB Output is correct
24 Correct 18 ms 15652 KB Output is correct
25 Correct 276 ms 18040 KB Output is correct
26 Correct 668 ms 20484 KB Output is correct
27 Correct 1762 ms 29676 KB Output is correct
28 Execution timed out 5047 ms 30132 KB Time limit exceeded
29 Halted 0 ms 0 KB -