oj.uz

Submission #676976

# Submission time Handle Problem Language Result Execution time Memory
676976 2023-01-02T00:23:20 Z rafatoa Tropical Garden (IOI11_garden) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

void answer(int ans);

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
    vector<vector<pair<int, int>>> adjin(n);
    vector<int> f(n), s(n, -1);
    vector<vector<int>> adj(2*n);
    for(int i=0; i<m; i++){
        adjin[r[i][0]].push_back({r[i][1], i});
        adjin[r[i][1]].push_back({r[i][0], i});
    }

    for(int i=0; i<n; i++){
        int c1 = 1e9, v1, c2 = 1e9, v2;
        for(auto &[v, c]:adjin[i]){
            if(c < c1){
                c2 = c1; v2 = v1;
                c1 = c; v1 = v;
            } else if(c < c2){
                c2 = c; v2 = v;
            }
        }

        if(c1 != 1e9) f[i] = v1;
        if(c2 != 1e9) s[i] = v2;
    }

    for(int i=0; i<n; i++){
        if(f[f[i]] != i || s[f[i]] == -1) adj[f[i]].push_back(i);
        else adj[f[i]+n].push_back(i);

        if(s[i] != -1){
            if(f[s[i]] != i || s[s[i]] == -1) adj[s[i]].push_back(i+n);
            else adj[s[i]+n].push_back(i+n);
        }
    }

    int c1 = -1, c2 = -1;
    vector<int> dist1(2*n, -1), dist2(2*n, -1);
    vector<bool> vis1(2*n), vis2(2*n);

    function<void(int, int)> dfs1 = [&](int s, int d){
        vis1[s] = 1;
        dist1[s] = d;
        for(auto &u:adj[s]){
            if(u == p) c1 = d+1;
            if(!vis1[u]) dfs1(u, d+1);
        }
    };

    function<void(int, int)> dfs2 = [&](int s, int d){
        vis2[s] = 1;
        dist2[s] = d;
        for(auto &u:adj[s]){
            if(u == p+n) c2 = d+1;
            if(!vis2[u]) dfs2(u, d+1);
        }
    };

    dfs1(p, 0); dfs2(p+n, 0);

    for(int t=0; t<q; t++){
        int ans = 0;
        for(int i=0; i<n; i++){
            bool ok = 0;
            if(dist1[i] != -1){
                if(c1 == -1 && dist1[i] == g[t]) ok = 1;
                if(c1 != -1 && (dist1[i]-g[t])%c1 == 0) ok = 1;
            }
            if(dist2[i] != -1){
                if(c2 == -1 && dist2[i] == g[t]) ok = 1;
                if(c2 != -1 && (dist2[i]-g[t])%c2 == 0) ok = 1;
            }
            if(ok) ans++;
        }
        answer(ans);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:27:28: warning: 'v2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |         if(c2 != 1e9) s[i] = v2;

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 -