oj.uz

답안 #669045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669045 2022-12-05T12:55:23 Z 1bin 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 5 ms 8276 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, p, r[NMAX][2], q, g[NMAX], e[NMAX][2], a, b, d[NMAX], dd[NMAX], cy2, cy;
vector<int> adj[NMAX];

void add(int a, int b){
    if(a % n == e[b][0]) adj[b + n].emplace_back(a);
    else adj[b].emplace_back(a);
    return;
}

void dfs(int x, int dist){
    d[x] = dist;
    for(int& nx : adj[x]){
        if(d[nx] == -1) dfs(nx, dist + 1);
        else if(nx == p) cy = dist + 1;
    }
    return;
}

/*
void answer(int x){
    cout << x << '\n';
    return;
}*/

void count_routes(int n_, int m_, int p_, int r_[][2], int q_, int g_[]){
    n = n_; m = m_; p = p_; q = q_;
    memset(e, -1, sizeof(e));
    for(int i = 0; i < m; i++){
        a = r_[i][0]; b = r_[i][1];
        if(e[a][0] == -1) e[a][0] = b;
        else if(e[a][1] == -1) e[a][1] = b;
        if(e[b][0] == -1) e[b][0] = a;
        else if(e[b][1] == -1) e[b][1] = a;
    }
    for(int i =0; i < n; i++)
        if(e[i][1] == -1) e[i][1] = e[i][0];
    for(int i = 0; i < n; i++)
        if(e[i][0] != -1){
            add(i, e[i][0]);
            add(i + n, e[i][1]);
        }
    memset(d, -1, sizeof(d));
    dfs(p, 0);
    swap(d, dd); cy2 = cy; cy = 0;
    memset(d, -1, sizeof(d));
    p += n; dfs(p, 0);
    for(int j = 0; j < q; j++){
        int ans = 0;
        a = g_[j];
        for(int i = 0; i < n; i++){
            if(d[i] == a || cy && a > d[i] && (a - d[i]) % cy == 0) ans++;
            else if(dd[i] == a || cy2 && a > dd[i] && (a - dd[i]) % cy2 == 0) ans++;
        }
        answer(ans);
    }
    return;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> p;
    for(int i = 0; i < m; i++) cin >> r[i][0] >> r[i][1];
    cin >> q;
    for(int i = 0; i < q; i++) cin >> g[i];
    count_routes(n, m, p, r, q, g);
    return 0;
}*/

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:60:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if(d[i] == a || cy && a > d[i] && (a - d[i]) % cy == 0) ans++;
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:61:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |             else if(dd[i] == a || cy2 && a > dd[i] && (a - dd[i]) % cy2 == 0) ans++;
      |                                   ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 5 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 5 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 5 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -