제출 #1006400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006400		whatthemomooofun1729	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	95 ms	40084 KiB

garden

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>

#define ff first
#define ss second
#define PB push_back
#define sz(x) int(x.size())
#define rsz resize
#define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation
#define all(x) (x).begin(),(x).end()
#define eps 1e-9

// more abusive notation (use at your own risk):
// #define int ll

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

// debugging
void __print(int x) {std::cerr << x;}
void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */
void __print(unsigned x) {std::cerr << x;}
void __print(ull x) {std::cerr << x;}
void __print(float x) {std::cerr << x;}
void __print(double x) {std::cerr << x;}
void __print(ld x) {std::cerr << x;}
void __print(char x) {std::cerr << '\'' << x << '\'';}
void __print(const char *x) {std::cerr << '\"' << x << '\"';}
void __print(const string& x) {std::cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';}
template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";}
void _print() {std::cerr << "]\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);}
void println() {std::cerr << ">--------------------<" << endl;}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */

// const variables
constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7

void setIO(const string& str) {// fast input/output
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (str.empty()) return;
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}

#include "garden.h"
#include "gardenlib.h"

struct DSU {
    int N;
    vi parent, siz;
    vc<array<int, 2>> change;
    DSU() {}
    DSU(int n) {
        N = n;
        parent.clear(), siz.clear();
        parent.rsz(N+1), siz.rsz(N+1, 1);
        iota(1 + all(parent), 1);
    }
    int find_set(int v) {
        if (parent[v] == v) return v;
        else return parent[v] = find_set(parent[v]);
    }
    bool unite(int a, int b) {
        a = find_set(a), b = find_set(b);
        if (a == b) return false;
        if (siz[a] < siz[b]) swap(a, b);
        parent[b] = a;
        siz[a] += siz[b];
        change.PB({a, b});
        return true;
    }
    void roll_back() {
        array<int, 2> p = change.back();
        change.pop_back();
        parent[p[1]] = p[1];
        siz[p[0]] -= siz[p[1]];
    }
    bool connected(int a, int b) {
        return find_set(a) == find_set(b);
    }
    bool connected() {
        return siz[find_set(1)] == N;
    }
};

int N, M, P, Q, L, temp_p;
vc<vc<pii>> adj; // the adjacency list
vi f, beauty, vst, dp, deg;
// f: the element that i is adjacent to
// beauty: the maximum beauty of any edge including i
// dp: the distance from v to p
// deg: degree of the vertices
// 2 * i -> most beautiful
// 2 * i + 1 -> second most beautiful
vc<vi> adj_; // the adjacency list of the modified graph
vc<pii> queries; // answering queries offline
vi ans; // answer for each query
DSU d;
bool in_cycle = false; // whether p is in the cycle or not

void answer_2005() {
    //debug(P);
    //debug(in_cycle);
    if (!in_cycle) { // then the portion of vertices that can reach P form a DAG
        vi cnt(2 * N, 0); // cnt[i] = number of paths with dp[v] = i
        for (int i = 0; i < N; ++i) {
            if (dp[2 * i] == INF) continue;
            cnt[dp[2 * i]]++;
        }
        for (int i = 0; i < Q; ++i) {
            if (queries[i].ff <= 2 * N - 1) ans[queries[i].ss] += cnt[queries[i].ff];
            // else ans[queries[i].ss] = 0 <---- old code, it doesn't make any sense because we have to add 0, not set it to 0
        }
    } else {
        vi cnt(L, 0); // cnt[i] = number of paths with dp[v] === i mod L, L = length of the cycle
        vi order(N);
        iota(all(order), 0);
        sort(all(order), [&](const int& a, const int& b) { // sort vertices in order of increasing distance
            return dp[2 * a] < dp[2 * b];
        });
        int ptr = 0;
        //debug(L);
        for (int i = 0; i < Q; ++i) {
            while (ptr < N && dp[2 * order[ptr]] <= queries[i].ff) { // while the distance is smaller than K
                cnt[dp[2 * order[ptr]]%L]++;
                ptr++;
            }
            //debug(cnt);
            //debug(queries[i].ff % L);
            ans[queries[i].ss] += cnt[queries[i].ff % L];
        }
    }
}

void construction() {
    d = DSU(2 * N); // keep track of all connected components
    adj_.rsz(2 * N), f.rsz(2 * N);
    for (int i = 0; i < N; ++i) {
        //debug(i);
        set<pii> st;
        fch(u, adj[i]) {
            st.insert({u.ss, u.ff}); // sort the adjacent vertices in order
        }
        //debug(st);
        // set values for f[i]
        if (sz(st) == 1) {
            int u = (*st.begin()).ss, w = (*st.begin()).ff;
            f[2 * i] = f[2 * i + 1] = 2 * u + (w == beauty[u]); // when beauty[u] == -1, it will just equal to 2 * u
        } else if (sz(st) >= 2) {
            int u1 = (*st.begin()).ss, u2 = (*next(st.begin())).ss;
            int w1 = (*st.begin()).ff, w2 = (*next(st.begin())).ff;
            f[2 * i] = 2 * u1 + (w1 == beauty[u1]);
            f[2 * i + 1] = 2 * u2 + (w2 == beauty[u2]);
        }
    }
    for (int i = 0; i < 2 * N; ++i) {
        adj_[f[i]].PB(i); // adj_: the reverse of f
        d.unite(f[i], i); // update
        //cerr << i << ' ' << f[i] << '\n';
    }
}

void compute() {
    in_cycle = false;
    vst.clear(), vst.rsz(2 * N, 0), dp.clear(), dp.rsz(2 * N, INF);
    for (int i = 0; i < 2 * N; ++i) {
        if (!vst[d.find_set(i)]) { // checking if this component is visited
            vst[d.find_set(i)] = 1;
            int t = f[i]; // tortoise and hare
            int h = f[f[i]];
            while (t != h) {
                t = f[t];
                h = f[f[h]];
            }
            L = 1; // the length of the cycle that P is in
            if (t == P) in_cycle = true;
            t = f[t];
            while (t != h) {
                L++;
                if (t == P) {
                    in_cycle = true; // DONT BREAK HERE
                }
                t = f[t];
            }
            if (in_cycle) {
                break; // because P is in exactly one cycle and we have found it
            }
        }
    }
    vst.clear(), vst.rsz(2 * N, 0);
    queue<int> q;
    q.push(P);
    dp[P] = 0;
    vst[P] = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        fch(u, adj_[v]) { // updating the shortest paths to each vertex
            if (!vst[u]) {
                vst[u] = 1;
                dp[u] = dp[v] + 1;
                q.push(u);
            }
        }
    }
}

void count_routes(int n, int m, int p, int R[][2], int q, int g[]) {
    N = n, M = m, P = p, Q = q;
    adj.rsz(N), queries.rsz(Q), beauty.rsz(N, M), ans.rsz(Q), deg.rsz(N, 0);
    for (int i = 0; i < M; ++i) {
        int a = R[i][0], b = R[i][1];
//        debug(i);
//        debug(a, b);
        assert(a < N && b < N);
        ckmin(beauty[a], i);
        ckmin(beauty[b], i);
        adj[a].PB({b, i});
        adj[b].PB({a, i});
        deg[a]++, deg[b]++;
    }
    for (int i = 0; i < N; ++i) {
        if (deg[i] == 1) {
            beauty[i] = -1; // only a single edge going from this vertex
        }
    }
    for (int i = 0; i < Q; ++i) {
        queries[i] = {g[i], i};
    }
    sort(all(queries)); // sort the queries by their value g[i]
    construction(); // construct the tree
    temp_p = P;
    P = 2 * P; // first, compute the answer assuming that all paths must end at 2 * P
    compute();
    answer_2005();
    P = 2 * temp_p + 1; // assume that all paths end at 2 * P + 1
    compute();
    answer_2005();
    for (int i = 0; i < Q; ++i) {
        answer(ans[i]);
    }
}
/*
int r[200000][2];
int g[200000];

signed main() { // TIME YOURSELF !!!
    setIO("");
    int n, m, p, q;
    cin >> n >> m >> p;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        r[i][0] = a, r[i][1] = b;
        //debug(r[i][0], r[i][1]);
    }
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> g[i];
        //debug(g[i]);
    }
    count_routes(n, m, p, r, q, g);
    return 0;
}*/

// TLE -> TRY NOT USING DEFINE INT LONG LONG
// CE -> CHECK LINE 45
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void setIO(const string&)':
garden.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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