oj.uz

Submission #16489

# Submission time Handle Problem Language Result Execution time Memory
16489 2015-08-26T11:28:32 Z khsoo01 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 32160 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 16 ms 15652 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 20 ms 15704 KB Output is correct
4 Correct 16 ms 15616 KB Output is correct
5 Correct 16 ms 15580 KB Output is correct
6 Correct 17 ms 15776 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15652 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 20 ms 15704 KB Output is correct
4 Correct 16 ms 15616 KB Output is correct
5 Correct 16 ms 15580 KB Output is correct
6 Correct 17 ms 15776 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16252 KB Output is correct
10 Correct 16 ms 15580 KB Output is correct
11 Correct 33 ms 18280 KB Output is correct
12 Correct 72 ms 20880 KB Output is correct
13 Correct 85 ms 29932 KB Output is correct
14 Correct 243 ms 30420 KB Output is correct
15 Correct 235 ms 31288 KB Output is correct
16 Correct 226 ms 28648 KB Output is correct
17 Correct 219 ms 27912 KB Output is correct
18 Correct 72 ms 20856 KB Output is correct
19 Correct 238 ms 30848 KB Output is correct
20 Correct 260 ms 31224 KB Output is correct
21 Correct 240 ms 28460 KB Output is correct
22 Correct 234 ms 27808 KB Output is correct
23 Correct 251 ms 32160 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15652 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 20 ms 15704 KB Output is correct
4 Correct 16 ms 15616 KB Output is correct
5 Correct 16 ms 15580 KB Output is correct
6 Correct 17 ms 15776 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16252 KB Output is correct
10 Correct 16 ms 15580 KB Output is correct
11 Correct 33 ms 18280 KB Output is correct
12 Correct 72 ms 20880 KB Output is correct
13 Correct 85 ms 29932 KB Output is correct
14 Correct 243 ms 30420 KB Output is correct
15 Correct 235 ms 31288 KB Output is correct
16 Correct 226 ms 28648 KB Output is correct
17 Correct 219 ms 27912 KB Output is correct
18 Correct 72 ms 20856 KB Output is correct
19 Correct 238 ms 30848 KB Output is correct
20 Correct 260 ms 31224 KB Output is correct
21 Correct 240 ms 28460 KB Output is correct
22 Correct 234 ms 27808 KB Output is correct
23 Correct 251 ms 32160 KB Output is correct
24 Correct 17 ms 15688 KB Output is correct
25 Correct 275 ms 18292 KB Output is correct
26 Correct 652 ms 21084 KB Output is correct
27 Correct 1770 ms 30172 KB Output is correct
28 Execution timed out 5086 ms 30992 KB Time limit exceeded
29 Halted 0 ms 0 KB -