oj.uz

Submission #598178

# Submission time Handle Problem Language Result Execution time Memory
598178 2022-07-17T18:50:05 Z snasibov05 Tropical Garden (IOI11_garden) C++14
0 / 100
 1 ms 468 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

void dfs(int cur, int t, vector<int>& d, int& c, vector<vector<int>>& ed){
    for (auto to : ed[cur]){
        if (to == t) {
            c = d[to] + 1;
            continue;
        }
        d[to] = d[cur] + 1;
        dfs(to, t, d, c, ed);
    }
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    const int lg = 32;

    vector<vector<int>> ed(n, vector<int>(2, -1));
    for (int i = 0; i < m; ++i) {
        if (ed[r[i][0]][0] == -1) ed[r[i][0]][0] = r[i][1];
        else if (ed[r[i][0]][1] == -1) ed[r[i][0]][1] = r[i][1];

        if (ed[r[i][1]][0] == -1) ed[r[i][1]][0] = r[i][0];
        else if (ed[r[i][1]][1] == -1) ed[r[i][1]][1] = r[i][0];
    }

    for (int i = 0; i < n; ++i) {
        if (ed[i][1] == -1) ed[i][1] = ed[i][0];
    }

    vector<vector<int>> gg(2*n);
    for (int i = 0; i < n; ++i){
        int t1 = ed[i][0];
        if (ed[t1][0] == i) gg[t1 + n].push_back(i);
        else gg[t1].push_back(i);

        int t2 = ed[i][1];
        if (ed[t2][0] == i) gg[t2 + n].push_back(i + n);
        else gg[t2].push_back(i + n);
    }

    vector<int> d1(2*n, 2*n + 5); d1[p] = 0;
    vector<int> d2(2*n, 2*n + 5); d2[p + n] = 0;
    int c1 = 2*n + 5, c2 = 2*n + 5;
    dfs(p, p, d1, c1, gg);
    dfs(p + n, p + n, d2, c2, gg);

    for (int i = 0; i < q; ++i){
        int res = 0;
        for (int j = 0; j < n; ++j){
            if (d1[j] == g[i] || (c1 <= 2*n && g[i] - d1[j] > 0 && (g[i] - d1[j]) % c1 == 0)) res++;
            else if (d2[j] == g[i] || (c2 <= 2*n && g[i] - d2[j] > 0 && (g[i] - d2[j]) % c2 == 0)) res++;
        }
        answer(res);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:19:15: warning: unused variable 'lg' [-Wunused-variable]
   19 |     const int lg = 32;
      |               ^~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -