oj.uz

Submission #16480

# Submission time Handle Problem Language Result Execution time Memory
16480 2015-08-26T11:15:58 Z khsoo01 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 33668 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 dist1[300005],dist2[300005],cyc_len[2];
bool state,in_cyc[2];

struct destination {
    int dist[300005],cyc_len=0;
    bool in_cyc=false;
}d[2];

void find_cyc(int idx) {
    if(vis[idx]==1) {
        if(!d[state].in_cyc && idx!=cn[p][state]) return;
        d[state].in_cyc=true;
        d[state].cyc_len++;
    }
    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 d[state].dist[idx]=0;
    if(vis[idx]) return d[state].dist[idx];
    vis[idx]++;
    return d[state].dist[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,k,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);
        d[0].dist[i]=-INF;
        d[1].dist[i]=-INF;
        d[0].dist[i+M]=-INF;
        d[1].dist[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<2;i++) {
        cyc_len[i]=d[i].cyc_len;
        in_cyc[i]=d[i].in_cyc;
    }
    for(j=0;j<2*m;j++) {
        dist1[j]=d[0].dist[j];
        dist2[j]=d[1].dist[j];
    }
    for(i=0;i<Q;i++) {
        cnt=0;
        for(j=0;j<n;j++) {
            tmp=cn[j][0];
            if(dist1[tmp]>=0) {
                if(dist1[tmp]==G[i]){
                    cnt++; continue;
                }
                if(dist1[tmp]<G[i] && in_cyc[0] && (G[i]-dist1[tmp])%cyc_len[0]==0) {
                    cnt++; continue;
                }
            }
            if(dist2[tmp]>=0) {
                if(dist2[tmp]==G[i]){
                    cnt++; continue;
                }
                if(dist2[tmp]<G[i] && in_cyc[1] && (G[i]-dist2[tmp])%cyc_len[1]==0) {
                    cnt++; continue;
                }
            }
        }
        answer(cnt);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:37:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,tmp; n=N; m=M; p=P;
             ^

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 15736 KB Output is correct
3 Correct 18 ms 15736 KB Output is correct
4 Correct 17 ms 15608 KB Output is correct
5 Correct 17 ms 15608 KB Output is correct
6 Correct 18 ms 15904 KB Output is correct
7 Correct 17 ms 15620 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16324 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 15736 KB Output is correct
3 Correct 18 ms 15736 KB Output is correct
4 Correct 17 ms 15608 KB Output is correct
5 Correct 17 ms 15608 KB Output is correct
6 Correct 18 ms 15904 KB Output is correct
7 Correct 17 ms 15620 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16324 KB Output is correct
10 Correct 16 ms 15608 KB Output is correct
11 Correct 33 ms 18444 KB Output is correct
12 Correct 66 ms 21556 KB Output is correct
13 Correct 82 ms 31224 KB Output is correct
14 Correct 229 ms 32632 KB Output is correct
15 Correct 252 ms 33168 KB Output is correct
16 Correct 218 ms 30220 KB Output is correct
17 Correct 211 ms 29584 KB Output is correct
18 Correct 64 ms 21384 KB Output is correct
19 Correct 233 ms 32596 KB Output is correct
20 Correct 252 ms 33276 KB Output is correct
21 Correct 227 ms 30220 KB Output is correct
22 Correct 245 ms 29460 KB Output is correct
23 Correct 239 ms 33572 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 15736 KB Output is correct
3 Correct 18 ms 15736 KB Output is correct
4 Correct 17 ms 15608 KB Output is correct
5 Correct 17 ms 15608 KB Output is correct
6 Correct 18 ms 15904 KB Output is correct
7 Correct 17 ms 15620 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 20 ms 16324 KB Output is correct
10 Correct 16 ms 15608 KB Output is correct
11 Correct 33 ms 18444 KB Output is correct
12 Correct 66 ms 21556 KB Output is correct
13 Correct 82 ms 31224 KB Output is correct
14 Correct 229 ms 32632 KB Output is correct
15 Correct 252 ms 33168 KB Output is correct
16 Correct 218 ms 30220 KB Output is correct
17 Correct 211 ms 29584 KB Output is correct
18 Correct 64 ms 21384 KB Output is correct
19 Correct 233 ms 32596 KB Output is correct
20 Correct 252 ms 33276 KB Output is correct
21 Correct 227 ms 30220 KB Output is correct
22 Correct 245 ms 29460 KB Output is correct
23 Correct 239 ms 33572 KB Output is correct
24 Correct 17 ms 15608 KB Output is correct
25 Correct 214 ms 18416 KB Output is correct
26 Correct 408 ms 21336 KB Output is correct
27 Correct 1913 ms 31020 KB Output is correct
28 Correct 2555 ms 32344 KB Output is correct
29 Execution timed out 5091 ms 33668 KB Time limit exceeded
30 Halted 0 ms 0 KB -