oj.uz

Submission #500659

# Submission time Handle Problem Language Result Execution time Memory
500659 2021-12-31T17:39:32 Z aryan12 Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 42096 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[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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 2 ms 5196 KB Output is correct
5 Correct 2 ms 5196 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 2 ms 5196 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 2 ms 5196 KB Output is correct
5 Correct 2 ms 5196 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 2 ms 5196 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5580 KB Output is correct
10 Correct 3 ms 5196 KB Output is correct
11 Correct 13 ms 10948 KB Output is correct
12 Correct 25 ms 15516 KB Output is correct
13 Correct 42 ms 31592 KB Output is correct
14 Correct 78 ms 39336 KB Output is correct
15 Correct 95 ms 40324 KB Output is correct
16 Correct 68 ms 32188 KB Output is correct
17 Correct 59 ms 29064 KB Output is correct
18 Correct 26 ms 16032 KB Output is correct
19 Correct 74 ms 39428 KB Output is correct
20 Correct 81 ms 40432 KB Output is correct
21 Correct 66 ms 32184 KB Output is correct
22 Correct 60 ms 28952 KB Output is correct
23 Correct 106 ms 42096 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 2 ms 5196 KB Output is correct
5 Correct 2 ms 5196 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 2 ms 5196 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 4 ms 5580 KB Output is correct
10 Correct 3 ms 5196 KB Output is correct
11 Correct 13 ms 10948 KB Output is correct
12 Correct 25 ms 15516 KB Output is correct
13 Correct 42 ms 31592 KB Output is correct
14 Correct 78 ms 39336 KB Output is correct
15 Correct 95 ms 40324 KB Output is correct
16 Correct 68 ms 32188 KB Output is correct
17 Correct 59 ms 29064 KB Output is correct
18 Correct 26 ms 16032 KB Output is correct
19 Correct 74 ms 39428 KB Output is correct
20 Correct 81 ms 40432 KB Output is correct
21 Correct 66 ms 32184 KB Output is correct
22 Correct 60 ms 28952 KB Output is correct
23 Correct 106 ms 42096 KB Output is correct
24 Correct 12 ms 5292 KB Output is correct
25 Correct 3414 ms 11300 KB Output is correct
26 Execution timed out 5051 ms 16104 KB Time limit exceeded
27 Halted 0 ms 0 KB -