oj.uz

답안 #16472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16472 2015-08-26T10:54:05 Z khsoo01 열대 식물원 (Tropical Garden) (IOI11_garden) C++
69 / 100
 5000 ms 31896 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++) {
            if(d[0].dist[cn[j][0]]==G[i])cnt++;
            else if(d[0].dist[cn[j][0]]>=0 && d[0].dist[cn[j][0]]<G[i] && d[0].in_cyc && (G[i]-d[0].dist[cn[j][0]])%d[0].cyc_len==0)cnt++;
            else if(d[1].dist[cn[j][0]]==G[i])cnt++;
            else if(d[1].dist[cn[j][0]]>=0 && d[1].dist[cn[j][0]]<G[i] && d[1].in_cyc && (G[i]-d[1].dist[cn[j][0]])%d[1].cyc_len==0)cnt++;
        }
        answer(cnt);
    }
}

Compilation message

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

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15684 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 16 ms 15652 KB Output is correct
4 Correct 16 ms 15548 KB Output is correct
5 Correct 16 ms 15656 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15640 KB Output is correct
9 Correct 20 ms 16240 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15684 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 16 ms 15652 KB Output is correct
4 Correct 16 ms 15548 KB Output is correct
5 Correct 16 ms 15656 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15640 KB Output is correct
9 Correct 20 ms 16240 KB Output is correct
10 Correct 17 ms 15688 KB Output is correct
11 Correct 32 ms 18044 KB Output is correct
12 Correct 64 ms 20432 KB Output is correct
13 Correct 86 ms 29656 KB Output is correct
14 Correct 245 ms 30084 KB Output is correct
15 Correct 258 ms 30484 KB Output is correct
16 Correct 232 ms 27780 KB Output is correct
17 Correct 223 ms 27164 KB Output is correct
18 Correct 65 ms 20316 KB Output is correct
19 Correct 241 ms 30164 KB Output is correct
20 Correct 250 ms 30340 KB Output is correct
21 Correct 229 ms 27576 KB Output is correct
22 Correct 227 ms 27148 KB Output is correct
23 Correct 247 ms 31300 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15684 KB Output is correct
2 Correct 16 ms 15708 KB Output is correct
3 Correct 16 ms 15652 KB Output is correct
4 Correct 16 ms 15548 KB Output is correct
5 Correct 16 ms 15656 KB Output is correct
6 Correct 17 ms 15836 KB Output is correct
7 Correct 16 ms 15580 KB Output is correct
8 Correct 17 ms 15640 KB Output is correct
9 Correct 20 ms 16240 KB Output is correct
10 Correct 17 ms 15688 KB Output is correct
11 Correct 32 ms 18044 KB Output is correct
12 Correct 64 ms 20432 KB Output is correct
13 Correct 86 ms 29656 KB Output is correct
14 Correct 245 ms 30084 KB Output is correct
15 Correct 258 ms 30484 KB Output is correct
16 Correct 232 ms 27780 KB Output is correct
17 Correct 223 ms 27164 KB Output is correct
18 Correct 65 ms 20316 KB Output is correct
19 Correct 241 ms 30164 KB Output is correct
20 Correct 250 ms 30340 KB Output is correct
21 Correct 229 ms 27576 KB Output is correct
22 Correct 227 ms 27148 KB Output is correct
23 Correct 247 ms 31300 KB Output is correct
24 Correct 18 ms 15700 KB Output is correct
25 Correct 237 ms 18052 KB Output is correct
26 Correct 482 ms 20500 KB Output is correct
27 Correct 1856 ms 29676 KB Output is correct
28 Correct 4714 ms 31124 KB Output is correct
29 Execution timed out 5062 ms 31896 KB Time limit exceeded
30 Halted 0 ms 0 KB -