Submission #971544

#	Time	Username	Problem	Language	Result	Execution time	Memory
971544		fzyzzz_z	Tropical Garden (IOI11_garden)	C++17	100 / 100	394 ms	67040 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

// void answer(int x) {
//     cout << "! " << x << '\n';
// }

using ll = long long; 

const int mxn = 150005; 

int g[2 * mxn], p[2 * mxn], vis[2 * mxn], c1[2 * mxn], val[2 * mxn]; 
vector<vector<int>> c2; 
vector<int> clen; 
vector<int> r[2 * mxn]; 

void dfs_find(int x) {
    if (vis[x]) return; 
    vis[x] = 1; 
    for (auto u: r[x]) {
        dfs_find(u); 
    }
    dfs_find(g[x]); 
}
void dfs_c1(int x, int d) {
    c1[d] += val[x];  
    for (auto u: r[x]) {
        dfs_c1(u, d + 1); 
    }
}
void dfs_c2(int x, int d, int f, int st) {
    while ((int) c2.back().size() <= d) c2.back().push_back(0); 
    c2.back()[d] += val[x]; 
    // cout << "!! " << x << ' ' << d << ' ' << f << ' ' << val[x] << '\n';
    for (auto u: r[x]) {
        if (x == f && u == st) continue; 
        dfs_c2(u, d + 1, f, st); 
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector<vector<int>> adj(N); 
    map<pair<int, int>, int> to; 
    vector<int> c; 
    for (int i = 0; i < M; ++i) {
        int x = R[i][0], y = R[i][1]; 
        to[{x, y}] = 2 * i; 
        to[{y, x}] = 2 * i + 1; 
        val[2 * i] = val[2 * i + 1] = 0; 
        adj[x].push_back(y); 
        adj[y].push_back(x); 
        if (x == P) c.push_back(2 * i + 1); 
        if (y == P) c.push_back(2 * i); 
    }
    for (int x = 0; x < N; ++x) {
        for (int i = 1; i < adj[x].size(); ++i) {
            g[to[{adj[x][i], x}]] = to[{x, adj[x][0]}]; 
        }
        g[to[{adj[x][0], x}]] = to[{x, adj[x][min((int)adj[x].size(), 2) - 1]}]; 
        val[to[{x, adj[x][0]}]] = 1; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        vis[x] = c1[x] = p[x] = 0; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        r[g[x]].push_back(x); 
        p[g[x]]++; 
    }

    queue<int> q; 
    for (int i = 0; i < 2 * M; ++i) {
        if (p[i] == 0) {
            q.push(i); 
        }
    }
    while (q.size()) {
        auto x = q.front(); 
        q.pop(); 
        p[g[x]]--; 
        if (p[g[x]] == 0) {
            q.push(g[x]); 
        }
    }

    
    int co = 0; 
    for (auto x: c) if (p[x]) co++; 


    for (auto x: c) {
        if (p[x] == 0) {
            dfs_c1(x, 0); 
        } else {
            c2.push_back({}); 
            dfs_c2(x, 0, g[x], x); 

            int cnt = 1; 
            int y = g[x]; 
            while (y != x) {
                y = g[y]; 
                cnt++; 
            }
            clen.push_back(cnt); 
            for (int i = 0; i + cnt < (int)c2.back().size(); ++i) {
                c2.back()[i + cnt] += c2.back()[i]; 
            }
        }
    }
    

    for (int i = 0; i < Q; ++i) {
        int v = G[i] - 1; 

        // int cans = 0; 
        // for (int st = 0; st < 2 * M; ++st) {
        //     if (val[st]) {
        //         int xx = st; 
        //         for (int t = 0; t < v; ++t) xx = g[xx]; 
        //         int ok = 0; 
        //         for (auto x: c) if (x == xx) ok = 1; 
        //         cans += ok; 
        //         // if (ok) cout << st << ' ';
        //     }
        // }
        // cout << "\n! " << cans << '\n'; 

        int ans = 0; 
        if (v < 2 * M) ans = c1[v]; 
        // cout << ans << '\n';

        for (int i = 0; i < (int) c2.size(); ++i) {
            int cl = clen[i]; 
            if (v < (int)c2[i].size()) ans += c2[i][v]; 
            else {
                int f = (v - c2[i].size()) / cl; 
                int vv = v - f * cl; 
                if (f > 0) vv += cl; 
                while (vv >= (int)c2[i].size()) vv -= cl; 
                ans += c2[i][vv]; 
            }

            // cout << ans << '\n';
        }

        answer(ans); 
    }
}

// int main() {
//     int n, m, p, q; 
//     cin >> n >> m >> p >> q; 
//     int e[m][2], g[q]; 
//     for (int i = 0; i < m; ++i) cin >> e[i][0] >> e[i][1]; 
//     for (int i = 0; i < q; ++i) cin >> g[i]; 
//     count_routes(n, m, p, e, q, g); 
// }

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

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