oj.uz

답안 #16477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16477 2015-08-26T11:11:22 Z khsoo01 열대 식물원 (Tropical Garden) (IOI11_garden) C++
69 / 100
 5000 ms 33644 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];

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++) {
            dist[i][j]=d[i].dist[j];
        }
    }
    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(in_cyc[0] && dist[0][tmp]>=0 && dist[0][tmp]<G[i] && (G[i]-dist[0][tmp])%cyc_len[0]==0) {
                cnt++; continue;
            }
            if(dist[1][tmp]==G[i]){
                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);
    }
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15776 KB Output is correct
2 Correct 17 ms 15700 KB Output is correct
3 Correct 17 ms 15812 KB Output is correct
4 Correct 16 ms 15680 KB Output is correct
5 Correct 18 ms 15564 KB Output is correct
6 Correct 18 ms 15880 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15756 KB Output is correct
9 Correct 21 ms 16376 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15776 KB Output is correct
2 Correct 17 ms 15700 KB Output is correct
3 Correct 17 ms 15812 KB Output is correct
4 Correct 16 ms 15680 KB Output is correct
5 Correct 18 ms 15564 KB Output is correct
6 Correct 18 ms 15880 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15756 KB Output is correct
9 Correct 21 ms 16376 KB Output is correct
10 Correct 17 ms 15728 KB Output is correct
11 Correct 31 ms 18316 KB Output is correct
12 Correct 74 ms 21252 KB Output is correct
13 Correct 84 ms 30968 KB Output is correct
14 Correct 243 ms 32264 KB Output is correct
15 Correct 257 ms 32884 KB Output is correct
16 Correct 232 ms 29972 KB Output is correct
17 Correct 221 ms 29380 KB Output is correct
18 Correct 74 ms 21320 KB Output is correct
19 Correct 243 ms 32340 KB Output is correct
20 Correct 257 ms 32772 KB Output is correct
21 Correct 234 ms 29908 KB Output is correct
22 Correct 227 ms 29072 KB Output is correct
23 Correct 234 ms 33644 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15776 KB Output is correct
2 Correct 17 ms 15700 KB Output is correct
3 Correct 17 ms 15812 KB Output is correct
4 Correct 16 ms 15680 KB Output is correct
5 Correct 18 ms 15564 KB Output is correct
6 Correct 18 ms 15880 KB Output is correct
7 Correct 16 ms 15608 KB Output is correct
8 Correct 17 ms 15756 KB Output is correct
9 Correct 21 ms 16376 KB Output is correct
10 Correct 17 ms 15728 KB Output is correct
11 Correct 31 ms 18316 KB Output is correct
12 Correct 74 ms 21252 KB Output is correct
13 Correct 84 ms 30968 KB Output is correct
14 Correct 243 ms 32264 KB Output is correct
15 Correct 257 ms 32884 KB Output is correct
16 Correct 232 ms 29972 KB Output is correct
17 Correct 221 ms 29380 KB Output is correct
18 Correct 74 ms 21320 KB Output is correct
19 Correct 243 ms 32340 KB Output is correct
20 Correct 257 ms 32772 KB Output is correct
21 Correct 234 ms 29908 KB Output is correct
22 Correct 227 ms 29072 KB Output is correct
23 Correct 234 ms 33644 KB Output is correct
24 Correct 18 ms 15608 KB Output is correct
25 Correct 263 ms 18536 KB Output is correct
26 Correct 600 ms 21324 KB Output is correct
27 Correct 1782 ms 31024 KB Output is correct
28 Execution timed out 5038 ms 32336 KB Time limit exceeded
29 Halted 0 ms 0 KB -