oj.uz

Submission #16490

# Submission time Handle Problem Language Result Execution time Memory
16490 2015-08-26T11:34:03 Z khsoo01 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 31416 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 15764 KB Output is correct
2 Correct 17 ms 15644 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 17 ms 15580 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 21 ms 16248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15764 KB Output is correct
2 Correct 17 ms 15644 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 17 ms 15580 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 21 ms 16248 KB Output is correct
10 Correct 16 ms 15572 KB Output is correct
11 Correct 31 ms 18104 KB Output is correct
12 Correct 66 ms 20804 KB Output is correct
13 Correct 87 ms 29880 KB Output is correct
14 Correct 241 ms 30344 KB Output is correct
15 Correct 256 ms 30472 KB Output is correct
16 Correct 228 ms 27856 KB Output is correct
17 Correct 219 ms 27220 KB Output is correct
18 Correct 71 ms 20368 KB Output is correct
19 Correct 236 ms 30052 KB Output is correct
20 Correct 262 ms 30472 KB Output is correct
21 Correct 227 ms 27744 KB Output is correct
22 Correct 255 ms 27040 KB Output is correct
23 Correct 247 ms 31416 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15764 KB Output is correct
2 Correct 17 ms 15644 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 17 ms 15580 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 21 ms 16248 KB Output is correct
10 Correct 16 ms 15572 KB Output is correct
11 Correct 31 ms 18104 KB Output is correct
12 Correct 66 ms 20804 KB Output is correct
13 Correct 87 ms 29880 KB Output is correct
14 Correct 241 ms 30344 KB Output is correct
15 Correct 256 ms 30472 KB Output is correct
16 Correct 228 ms 27856 KB Output is correct
17 Correct 219 ms 27220 KB Output is correct
18 Correct 71 ms 20368 KB Output is correct
19 Correct 236 ms 30052 KB Output is correct
20 Correct 262 ms 30472 KB Output is correct
21 Correct 227 ms 27744 KB Output is correct
22 Correct 255 ms 27040 KB Output is correct
23 Correct 247 ms 31416 KB Output is correct
24 Correct 18 ms 15608 KB Output is correct
25 Correct 276 ms 18044 KB Output is correct
26 Correct 655 ms 20500 KB Output is correct
27 Correct 1823 ms 29664 KB Output is correct
28 Execution timed out 5042 ms 30084 KB Time limit exceeded
29 Halted 0 ms 0 KB -