Submission #669047

#	Time	Username	Problem	Language	Result	Execution time	Memory
669047		1bin	Tropical Garden (IOI11_garden)	C++14	100 / 100	2606 ms	31532 KiB

garden

#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 = 3e5 + 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 (stderr)

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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31