Submission #500659

#	Time	Username	Problem	Language	Result	Execution time	Memory
500659		aryan12	Tropical Garden (IOI11_garden)	C++17	69 / 100	5051 ms	42096 KiB

garden

#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[31][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 < 31; 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 < N; j++) {
            int diff = G[i], idx = g[j][0].second;
            for(int k = 30; k >= 0; k--) {
                if(diff >= (1 << k)) {
                    diff -= (1 << k);
                    idx = parent[k][idx];
                }
            }
            if(edges[idx].second == P) {
                ans++;
            }
            //cout << "ans = " << ans << "\n";
        }
        answer(ans);
    }
}

Compilation message (stderr)

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: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31