oj.uz

답안 #639742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639742 2022-09-11T12:43:49 Z Hacv16 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 88 ms 38668 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e5 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << ": " << "[ " << x << " ]\n"

void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
    vector<vector<int>> adj(n), rev(2 * n);
    vector<int> pai(2 * n, -1);

    for(int i = 0; i < m; i++){
        int u = r[i][0], v = r[i][1];
        if(sz(adj[u]) < 2) adj[u].pb(v);
        if(sz(adj[v]) < 2) adj[v].pb(u);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < min(2, sz(adj[i])); j++){
            int v = adj[i][j];
            int cur = (adj[v][0] == i) * n + v;
            pai[j * n + i] = cur;
        }
    }

    for(int i = n; i < 2 * n; i++)
        if(pai[i] == -1) pai[i] = pai[i - n];

    for(int i = 0; i < 2 * n; i++)
        rev[pai[i]].pb(i); 
    
    vector<bool> seen(2 * n);

    function<void(int, int , int&, vector<int>&)> 
    dfs = [&](int u, int end, int &len, vector<int> &dist){
        seen[u] = true;

        for(auto v : rev[u]){
            if(v == end){
                len = dist[u] + 1;
                return;
            }

            if(seen[v]) continue;

            dist[v] = dist[u] + 1;
            dfs(v, end, len, dist);
        }
    };

    vector<int> cyc(2, INF);
    vector<vector<int>> dist(2, vector<int>(2 * n, -1));

    dist[0][p] = dist[1][p + n] = 0;
    dfs(p, p, cyc[0], dist[0]);
    fill(all(seen), false);
    dfs(p + n, p + n, cyc[1], dist[1]);

    vector<vector<int>> fdist(2, vector<int>(2 * MAX));

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
            if(dist[i][j] == -1) continue;
            fdist[i][dist[i][j]]++;
        }
    }

    for(int i = 0; i < q; i++){
        int k = qrs[i], ans = 0;
        
        for(int j = 0; j < 2; j++){
            for(int d = k % cyc[j]; d <= min(n, k); d += cyc[j])
                ans += fdist[j][d];
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 12 ms 9268 KB Output is correct
12 Correct 24 ms 12052 KB Output is correct
13 Correct 52 ms 38668 KB Output is correct
14 Incorrect 88 ms 29276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 12 ms 9268 KB Output is correct
12 Correct 24 ms 12052 KB Output is correct
13 Correct 52 ms 38668 KB Output is correct
14 Incorrect 88 ms 29276 KB Output isn't correct
15 Halted 0 ms 0 KB -