oj.uz

Submission #500658

# Submission time Handle Problem Language Result Execution time Memory
500658 2021-12-31T17:38:34 Z aryan12 Tropical Garden (IOI11_garden) C++17
49 / 100
 26 ms 13120 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 < N; j++) {
            int diff = G[i], idx = g[j][0].second;
            for(int k = 19; 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 5260 KB Output is correct
2 Correct 3 ms 5260 KB Output is correct
3 Correct 4 ms 5244 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5128 KB Output is correct
6 Correct 4 ms 5396 KB Output is correct
7 Correct 3 ms 5128 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5400 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5260 KB Output is correct
2 Correct 3 ms 5260 KB Output is correct
3 Correct 4 ms 5244 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5128 KB Output is correct
6 Correct 4 ms 5396 KB Output is correct
7 Correct 3 ms 5128 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5400 KB Output is correct
10 Correct 3 ms 5128 KB Output is correct
11 Correct 11 ms 9412 KB Output is correct
12 Incorrect 26 ms 13120 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5260 KB Output is correct
2 Correct 3 ms 5260 KB Output is correct
3 Correct 4 ms 5244 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5128 KB Output is correct
6 Correct 4 ms 5396 KB Output is correct
7 Correct 3 ms 5128 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 4 ms 5400 KB Output is correct
10 Correct 3 ms 5128 KB Output is correct
11 Correct 11 ms 9412 KB Output is correct
12 Incorrect 26 ms 13120 KB Output isn't correct
13 Halted 0 ms 0 KB -