oj.uz

Submission #669046

# Submission time Handle Problem Language Result Execution time Memory
669046 2022-12-05T12:57:12 Z 1bin Tropical Garden (IOI11_garden) C++14
49 / 100
 40 ms 23084 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] && d[i] != -1 && (a - d[i]) % cy == 0) ans++;
            else if(dd[i] == a || cy2 && a > dd[i] && dd[i] != -1 && (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:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if(d[i] == a || cy && a > d[i] && d[i] != -1 && (a - d[i]) % cy == 0) ans++;
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:61:67: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |             else if(dd[i] == a || cy2 && a > dd[i] && dd[i] != -1 && (a - dd[i]) % cy2 == 0) ans++;
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8080 KB Output is correct
5 Correct 4 ms 8120 KB Output is correct
6 Correct 5 ms 8220 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 6 ms 8276 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8080 KB Output is correct
5 Correct 4 ms 8120 KB Output is correct
6 Correct 5 ms 8220 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 6 ms 8276 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 10 ms 9500 KB Output is correct
12 Correct 20 ms 10488 KB Output is correct
13 Correct 37 ms 23084 KB Output is correct
14 Runtime error 40 ms 17368 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 6 ms 8148 KB Output is correct
4 Correct 4 ms 8080 KB Output is correct
5 Correct 4 ms 8120 KB Output is correct
6 Correct 5 ms 8220 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 6 ms 8276 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 10 ms 9500 KB Output is correct
12 Correct 20 ms 10488 KB Output is correct
13 Correct 37 ms 23084 KB Output is correct
14 Runtime error 40 ms 17368 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -