oj.uz

답안 #49452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49452 2018-05-29T06:27:03 Z ho94949 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 9 ms 7800 KB 
#include "garden.h"
#include "gardenlib.h"
#include <cstdio>
#include <vector>
#include <initializer_list>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 151515;
int N;
int minv1[MAXN], minv2[MAXN];

int outlist[2*MAXN];
vector<int> inlist[2*MAXN];
bool visit[2*MAXN];
int ans1[2*MAXN], ans2[2*MAXN];
void run(int P, int dist, int *ans, int &res, int oP)
{
    if(visit[P])
    {
        if(P == oP) res = dist;
        return;
    }
    visit[P] = true;
    if(P<N) ans[dist]++;
    for(auto x: inlist[P])
        run(x, dist+1, ans, res, oP);
}

void count_routes(int _N, int M, int P, int R[][2], int Q, int G[])
{
    N = _N;
    for(int i=0; i<N; ++i) minv1[i] = minv2[i] = -1;
    for(int i=0; i<M; ++i)
    {
        int u = R[i][0], v = R[i][1];
        for(int x: {u, v})
        {
            int y = u+v-x;
            if(minv1[x] == -1) minv1[x] = y;
            else if(minv2[x] == -1) minv2[x] = y;
        }
    }
    for(int i=0; i<N; ++i) if(minv2[i] == -1) minv2[i] = minv1[i];
    for(int i=0; i<2*N; ++i)
    {
        int to = (i<N)?minv1[i%N]:minv2[i%N];
        if(i%N == minv1[to]) to += N;
        outlist[i] = to;
        inlist[to].push_back(i);
    }
    
    int res1 = 0x3f3f3f3f, res2 = 0x3f3f3f3f;
    run(P, 0, ans1, res1, P);
    for(int i=0; i<2*N; ++i) visit[i] = false;
    run(P+N, 0, ans2, res2, P+N);
    
    for(int i=2*N-1; i>=res1; --i)
        ans1[i-res1] += ans1[i];
    for(int i=2*N-1; i>=res2; --i)
        ans2[i-res2] += ans2[i];
    
    for(int i=0; i<Q; ++i)
    {
        int ans = 0;
        if(G[i] < 2*N) ans += ans1[G[i]];
        else
        {
            int maxidx = (G[i]-(2*N-1))%res1 + (2*N-1) - res1;
            if(maxidx >= 0) ans += ans1[maxidx];
        }
        if(G[i] < 2*N) ans += ans2[G[i]];
        else
        {
            int maxidx = (G[i]-(2*N-1))%res2 + (2*N-1) - res2;
            if(maxidx >= 0) ans += ans2[maxidx];
        }
        answer(ans);
    }    
    return;
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -