oj.uz

답안 #717865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
717865 2023-04-02T16:55:33 Z TheSahib 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 6 ms 9684 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define oo 1e9

using namespace std;

bool comp(pii a, pii b){
    return a.second < b.second;
}

const int MAX = 3e5 + 5;

int n, m, f;
vector<pii> g[MAX];
int tmpG[MAX];

int revG[MAX];
pii dist[MAX];

int dfs(int node, int d){
    if(revG[node] != f && dist[revG[node]].first < d + 1) return 0;
    dist[node].first = min(dist[node].first, d);
    
    int c = 0;
    if(revG[node] == f){
        c = d + 1;
    }
    else{
        c = dfs(revG[node], d + 1);
    }

    if(c){
        dist[node].second = c - dist[node].first;
    }
    return c;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    fill(dist, dist + MAX, make_pair(oo, oo));
    f = P;
    n = N;
    m = M;

    for (int i = 0; i < m; i++)
    {
        g[R[i][0]].push_back({R[i][1], i});
        g[R[i][1]].push_back({R[i][0], i});
    }
    for (int i = 0; i < n; i++)
    {
        sort(g[i].begin(), g[i].end(), comp);
    }
    for (int i = 0; i < n; i++)
    {
        if(g[i][0].second == g[g[i][0].first][0].second){
            tmpG[i] = g[i][0].first + n;
        }
        else{
            tmpG[i] = g[i][0].first;
        }
        if(g[i].size() >= 2){
            if(g[i][1].second == g[g[i][1].first][0].second){
                tmpG[i + n] = g[i][1].first + n;
            }
            else{
                tmpG[i + n] = g[i][1].first;
            }
        }
        if(g[i].size() == 1){
            tmpG[i + n] = tmpG[i];
        }
    }
    for (int i = 0; i < (n << 1); i++)
    {
        revG[tmpG[i]] = i;
    }
    
    dfs(f, 0);
    dfs(f + n, 0);
    for (int j = 0; j < Q; j++)
    {
        int ans = 0;
        for (int i = 0; i < (n << 1); i++)
        {
            if(dist[i].first == oo) continue;
            if(dist[i].second == oo) ans += (dist[i].first == G[j]);
            else if(G[j] - dist[i].first >= 0) ans += ((G[j] - dist[i].first) % dist[i].second) == 0;
        }
        answer(ans);
    }
    
}

Subtask #1
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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