Submission #380990

#	Time	Username	Problem	Language	Result	Execution time	Memory
380990		parsabahrami	Tropical Garden (IOI11_garden)	C++17	49 / 100	18 ms	11884 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
 
const int N = 2020;
ll dp[N][N]; int n, m, q, mn[N]; vector<int> adj2[N], adj[N];

void count_routes(int _n, int _m, int P, int R[][2], int _q, int G[]) {
    n = _n, m = _m, q = _q;
    fill(mn, mn + N, 1e9);
    for (int i = 0; i < m; i++) {
        adj2[R[i][0]].push_back(i), mn[R[i][0]] = min(mn[R[i][0]], i);
        adj2[R[i][1]].push_back(i), mn[R[i][1]] = min(mn[R[i][1]], i);
    }
    for (int i = 0; i < n * 2; i++) {
        if (i >= n) {
            int v = R[mn[i - n]][0] ^ (i - n) ^ R[mn[i - n]][1];
            if (mn[i - n] == mn[v]) adj[i].push_back(v);
            else adj[i].push_back(v + n);
        } else {
            int sec = -1;
            for (int id : adj2[i]) 
                if (id != mn[i]) { sec = id; break; }
            if (!~sec) sec = mn[i];
            int v = R[sec][0] ^ i ^ R[sec][1];
            if (sec == mn[v]) adj[i].push_back(v);
            else adj[i].push_back(v + n);
        }
    }
    dp[P][0] = dp[P + n][0] = 1;
    for (int i = 1; i < 200; i++) 
        for (int j = 0; j < 2 * n; j++) dp[j][i] += dp[adj[j][0]][i - 1];
    for (int i = 0; i < q; i++) {
        int sum = 0;
        for (int j = n; j < 2 * n; j++) sum += dp[j][G[i]];
        answer(sum);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31