oj.uz

Submission #16469

# Submission time Handle Problem Language Result Execution time Memory
16469 2015-08-26T10:46:53 Z khsoo01 Tropical Garden (IOI11_garden) C++
69 / 100
 5000 ms 32428 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;
bool state;

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; 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<Q;i++) {
        cnt=0;
        for(j=0;j<n;j++) {
            flag=0;
            for(k=0;k<2;k++) {
                if(d[k].dist[cn[j][0]]<0) continue;
                if(d[k].dist[cn[j][0]]==G[i])flag=1;
                if(d[k].dist[cn[j][0]]<G[i] && d[k].in_cyc && (G[i]-d[k].dist[cn[j][0]])%d[k].cyc_len==0)flag=1;
            }
            if(flag)cnt++;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15708 KB Output is correct
2 Correct 17 ms 15736 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15608 KB Output is correct
6 Correct 20 ms 15816 KB Output is correct
7 Correct 16 ms 15652 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15708 KB Output is correct
2 Correct 17 ms 15736 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15608 KB Output is correct
6 Correct 20 ms 15816 KB Output is correct
7 Correct 16 ms 15652 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16216 KB Output is correct
10 Correct 17 ms 15684 KB Output is correct
11 Correct 32 ms 17912 KB Output is correct
12 Correct 73 ms 20612 KB Output is correct
13 Correct 82 ms 30280 KB Output is correct
14 Correct 235 ms 31064 KB Output is correct
15 Correct 262 ms 31576 KB Output is correct
16 Correct 229 ms 28752 KB Output is correct
17 Correct 230 ms 28120 KB Output is correct
18 Correct 74 ms 20852 KB Output is correct
19 Correct 245 ms 31104 KB Output is correct
20 Correct 249 ms 31560 KB Output is correct
21 Correct 231 ms 28840 KB Output is correct
22 Correct 233 ms 28048 KB Output is correct
23 Correct 242 ms 32428 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15708 KB Output is correct
2 Correct 17 ms 15736 KB Output is correct
3 Correct 17 ms 15736 KB Output is correct
4 Correct 16 ms 15608 KB Output is correct
5 Correct 16 ms 15608 KB Output is correct
6 Correct 20 ms 15816 KB Output is correct
7 Correct 16 ms 15652 KB Output is correct
8 Correct 17 ms 15736 KB Output is correct
9 Correct 22 ms 16216 KB Output is correct
10 Correct 17 ms 15684 KB Output is correct
11 Correct 32 ms 17912 KB Output is correct
12 Correct 73 ms 20612 KB Output is correct
13 Correct 82 ms 30280 KB Output is correct
14 Correct 235 ms 31064 KB Output is correct
15 Correct 262 ms 31576 KB Output is correct
16 Correct 229 ms 28752 KB Output is correct
17 Correct 230 ms 28120 KB Output is correct
18 Correct 74 ms 20852 KB Output is correct
19 Correct 245 ms 31104 KB Output is correct
20 Correct 249 ms 31560 KB Output is correct
21 Correct 231 ms 28840 KB Output is correct
22 Correct 233 ms 28048 KB Output is correct
23 Correct 242 ms 32428 KB Output is correct
24 Correct 18 ms 15600 KB Output is correct
25 Correct 300 ms 18276 KB Output is correct
26 Correct 657 ms 21080 KB Output is correct
27 Correct 2287 ms 30572 KB Output is correct
28 Execution timed out 5024 ms 30092 KB Time limit exceeded
29 Halted 0 ms 0 KB -