oj.uz

답안 #1105183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105183 2024-10-25T16:11:31 Z anarch_y 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 27 ms 11600 KB 
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    int n = N, m = M;
    vector<pair<int, int>> vec[n];
    int mn[n] = {};
    for(int i=1; i<=m; i++){
        int a, b; a = R[i-1][0], b = R[i-1][1];
        vec[a].pb({b, i}); vec[b].pb({a, i});
        if(mn[a] == 0) mn[a] = i;
        if(mn[b] == 0) mn[b] = i; 
    } 
    int to[2*n] = {};
    for(int a=0; a<n; a++){
        auto [b, i] = vec[a][0];
        if(mn[b] == i) to[a] = n+b;
        else to[a] = b;
        if(sz(vec[a]) >= 2){
            auto [c, j] = vec[a][1];
            if(mn[c] == j) to[n+a] = n+c;
            else to[n+a] = c; 
        }
        else{
            if(mn[b] == i) to[n+a] = n+b;
            else to[n+a] = b;
        }
    }
    int succ[2*n][20] = {};
    for(int a=0; a<2*n; a++){
        succ[a][0] = to[a];
    }
    for(int i=1; i<20; i++){
        for(int a=0; a<2*n; a++){
            succ[a][i] = succ[succ[a][i-1]][i-1];
        }
    }
    int p = P;
    int q = Q;
    int qry[q] = {};
    for(int i=0; i<q; i++) qry[i] = G[i];
    for(int i=0; i<q; i++){
        int k = qry[i];
        int ans = 0;
        for(int a=0; a<n; a++){
            int x = a;
            for(int i=0; i<20; i++){
                if(k & (1<<i)) x = succ[x][i];
            }
            if(x == p or x == n+p) ans++;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 12 ms 7760 KB Output is correct
12 Incorrect 27 ms 11600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 12 ms 7760 KB Output is correct
12 Incorrect 27 ms 11600 KB Output isn't correct
13 Halted 0 ms 0 KB -