oj.uz

Submission #639742

# Submission time Handle Problem Language Result Execution time Memory
639742 2022-09-11T12:43:49 Z Hacv16 Tropical Garden (IOI11_garden) C++17
49 / 100
 88 ms 38668 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e5 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << ": " << "[ " << x << " ]\n"

void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
    vector<vector<int>> adj(n), rev(2 * n);
    vector<int> pai(2 * n, -1);

    for(int i = 0; i < m; i++){
        int u = r[i][0], v = r[i][1];
        if(sz(adj[u]) < 2) adj[u].pb(v);
        if(sz(adj[v]) < 2) adj[v].pb(u);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < min(2, sz(adj[i])); j++){
            int v = adj[i][j];
            int cur = (adj[v][0] == i) * n + v;
            pai[j * n + i] = cur;
        }
    }

    for(int i = n; i < 2 * n; i++)
        if(pai[i] == -1) pai[i] = pai[i - n];

    for(int i = 0; i < 2 * n; i++)
        rev[pai[i]].pb(i); 
    
    vector<bool> seen(2 * n);

    function<void(int, int , int&, vector<int>&)> 
    dfs = [&](int u, int end, int &len, vector<int> &dist){
        seen[u] = true;

        for(auto v : rev[u]){
            if(v == end){
                len = dist[u] + 1;
                return;
            }

            if(seen[v]) continue;

            dist[v] = dist[u] + 1;
            dfs(v, end, len, dist);
        }
    };

    vector<int> cyc(2, INF);
    vector<vector<int>> dist(2, vector<int>(2 * n, -1));

    dist[0][p] = dist[1][p + n] = 0;
    dfs(p, p, cyc[0], dist[0]);
    fill(all(seen), false);
    dfs(p + n, p + n, cyc[1], dist[1]);

    vector<vector<int>> fdist(2, vector<int>(2 * MAX));

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
            if(dist[i][j] == -1) continue;
            fdist[i][dist[i][j]]++;
        }
    }

    for(int i = 0; i < q; i++){
        int k = qrs[i], ans = 0;
        
        for(int j = 0; j < 2; j++){
            for(int d = k % cyc[j]; d <= min(n, k); d += cyc[j])
                ans += fdist[j][d];
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 12 ms 9268 KB Output is correct
12 Correct 24 ms 12052 KB Output is correct
13 Correct 52 ms 38668 KB Output is correct
14 Incorrect 88 ms 29276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5268 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 4 ms 5308 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 12 ms 9268 KB Output is correct
12 Correct 24 ms 12052 KB Output is correct
13 Correct 52 ms 38668 KB Output is correct
14 Incorrect 88 ms 29276 KB Output isn't correct
15 Halted 0 ms 0 KB -