Submission #1305032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305032		nicolo_010	Tropical Garden (IOI11_garden)	C++20	69 / 100	5093 ms	148004 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int mxN = 150000+5;

pii lift[3*mxN][31];
int rev[3*mxN];
vector<vector<int>> adj;

void count_routes(int N, int M, int p, int r[][2], int q, int g[]) {
    int n = N, m = M;
    vector<vector<int>> adj(n);
    map<pii, int> mp;
    map<int, pii> rev;
    int id=0;
    for (int i=0; i<m; i++) {
        int a, b;
        a = r[i][0];
        b = r[i][1];
        if (adj[a].size()<2) {
            adj[a].push_back(b);
            mp[{b, a}] = id;
            rev[id] = {b, a};
            id++;
        }
        if (adj[b].size()<2) {
            adj[b].push_back(a);
            mp[{a, b}] = id;
            rev[id] = {a, b};
            id++;
        }
    }
    for (int i=0; i<n; i++) {
        mp[{i, i}] = id;
        rev[id] = {i, i};
        id++;
    }
    for (int i=0; i<id; i++) {
        int a = rev[i].first;
        int b = rev[i].second;
        //Estado (a, b) llegue a a desde b
        if (adj[a].size()==1) {
            lift[i][0].first = mp[{adj[a][0], a}];
            lift[i][0].second = i;
        }
        else {
            lift[i][0].first = (b==adj[a][0] ? mp[{adj[a][1], a}] : mp[{adj[a][0], a}]);
            lift[i][0].second = i;
        }
    }
    for (int j=1; j<31; j++) {
        for (int i=0; i<id; i++) {
            int a = lift[i][j].first;
            int b = lift[i][j].second;
            lift[i][j].first = lift[lift[i][j-1].first][j-1].first;
            lift[i][j].second = lift[lift[i][j-1].first][j-1].second;
        }
    }
    //cout << rev[aux].first << " " << rev[aux].second << endl;
    for (int i=0; i<q; i++) {
        int k = g[i];
        int ans=0;
        for (int j=0; j<id; j++) {
            int node = j;
            int u, v;
            u = rev[j].first;
            v = rev[j].second;
            if (u!=v) continue;
            //cout << rev[node].first << " " << rev[node].second << endl;
            for (int b=0; b<31; b++) {
                if (k&(1<<b)) {
                    node = lift[node][b].first;
                    //cout << node << " " << u << " " << v << endl;
                }
            }
            int a = rev[node].first;
            int b = rev[node].second;
            //cout << node << " " << a << " " << b << endl;
            if (a == p) ans++;
        }   
        answer(ans);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31