oj.uz

Submission #500636

# Submission time Handle Problem Language Result Execution time Memory
500636 2021-12-31T16:07:25 Z aryan12 Tropical Garden (IOI11_garden) C++17
0 / 100
 3 ms 5324 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
vector<pair<int, int> > g[MAXN];
vector<pair<int, int> > edges;
bool vis[MAXN * 2];
int parent[20][MAXN * 2];

void dfs(int node, int par, int idx) {
    //cout << "node = " << node << "\n";
    vis[idx] = true;
    for(int i = 0; i < g[node].size(); i++) {
        if(g[node][i].first == par && g[node].size() != 1) {
            continue;
        }
        parent[0][idx] = g[node][i].second;
        if(vis[g[node][i].second]) return;
        dfs(g[node][i].first, node, g[node][i].second);
        break;
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    int cnt = 0;
    for(int i = 0; i < M; i++) {
        if(g[R[i][0]].size() < 2) {
            g[R[i][0]].push_back(make_pair(R[i][1], cnt++));
            edges.push_back(make_pair(R[i][0], R[i][1]));
        }
        if(g[R[i][1]].size() < 2) {
            g[R[i][1]].push_back(make_pair(R[i][0], cnt++));
            edges.push_back(make_pair(R[i][1], R[i][0]));
        }
    }
    /*for(int i = 0; i < N; i++) {
        cout << "Source: " << i << "\n";
        for(int j = 0; j < g[i].size(); j++) {
            cout << g[i][j].first << ", " << g[i][j].second <<  "\n";
        }
        cout << "\n\n";
    }*/
    for(int i = 0; i < cnt; i++) {
        if(!vis[i]) {
            dfs(edges[i].second, edges[i].first, i);
        }
    }
    /*cout << "Immediate parents\n";
    for(int i = 0; i < cnt; i++) {
        cout << edges[i].first << "->" << edges[i].second << ", par = " << parent[0][i] << "\n";
       // cout << parent[0][i] << " ";
    }
    cout << "\n";*/
    for(int i = 1; i < 20; i++) {
        for(int j = 0; j < cnt; j++) {
            assert(parent[i - 1][j] >= 0 && parent[i - 1][j] < cnt);
            parent[i][j] = parent[i - 1][parent[i - 1][j]];
        }
    }
    for(int i = 0; i < Q; i++) {
        int ans = 0;
        G[i]--;
        for(int j = 0; j < cnt; j++) {
            int diff = G[i], idx = j;
            for(int k = 19; k >= 0; k--) {
                if(diff >= (1 << k)) {
                    diff -= (1 << k);
                    idx = parent[k][idx];
                }
            }
            if(edges[idx].second == P) {
                ans++;
            }
        }
        answer(ans);
    }
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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