제출 #1366951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366951		AzeTurk810	다리 (APIO19_bridges)	C++20	100 / 100	1126 ms	74880 KiB

bridges

#include <cmath>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif

constexpr int N = 1e5 + 5;
;
int _n, _m;
char changed[N];
int v[N], u[N], t[N], x[N], y[N], w[N], ans[N], p[N], sz[N];
vector<int> ext[N];

struct DSU_roll {
    int n, c;
    vector<pair<int, int>> H;
    DSU_roll(int _n) : n(_n), c(_n) {
        for (int v = 1; v <= _n; v++) {
            p[v] = v;
        }
    }

    void init() {
        for (size_t v = 1; v <= _n; v++) {
            p[v] = v;
        }
        for (size_t v = 1; v <= _n; v++) {
            sz[v] = 1;
        }
    }
    int find(int v) {
        if (p[v] == v)
            return v;
        return find(p[v]);
    }

    char Union(int v, int u) {
        v = find(v), u = find(u);
        if (sz[v] < sz[u])
            swap(u, v);
        if (u == v)
            return false;
        p[u] = v;
        sz[v] += sz[u];
        c--;
        H.push_back(make_pair(v, u));
        return true;
    }

    void roll(int x) {
        while (H.size() > x) {
            auto [v, u] = H.back();
            H.pop_back();
            c++;
            sz[v] -= sz[u];
            p[u] = u;
        }
    }
};

inline void systemd() {
}

char solve() {
    if (!(cin >> _n >> _m))
        return 1;
    systemd();
    for (size_t i = 1; i <= _m; i++) {
        cin >> u[i] >> v[i] >> w[i];
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }
    int D = 1050;
    DSU_roll dsu(_n + 1);
    dsu.init();
    for (int l = 1; l <= q; l += D) {
    dsu.init();
        fill(changed + 1, changed + _m + 1, 0);
        int r = min(q, l + D - 1);
        vector<int> ask, upd, unchanged;
        for (size_t i = l; i <= r; i++) {
            if (t[i] == 1) {
                changed[x[i]] = true;
                upd.push_back(i);
            } else {
                ask.push_back(i);
            }
        }
        for (size_t i = 1; i <= _m; i++) {
            if (!changed[i])
                unchanged.push_back(i);
        }
        for (size_t i = l; i <= r; i++) {
            if (t[i] == 1) {
                w[x[i]] = y[i];
                ans[i] = -1;
            } else {
                ext[i - l].clear();
                for (auto &ind : upd) {
                    if (w[x[ind]] >= y[i]) {
                        ext[i - l].push_back(x[ind]);
                    }
                }
            }
        }
        sort(ask.begin(), ask.end(), [&](int &l, int &r) {
            return y[l] > y[r];
        });
        sort(unchanged.begin(), unchanged.end(), [&](int &l, int &r) {
            return w[l] > w[r];
        });
        int idx = 0;
        for (auto &i : ask) {
            dbg(i);
            while (idx < unchanged.size() && w[unchanged[idx]] >= y[i]) {
                dsu.Union(u[unchanged[idx]], v[unchanged[idx]]);
                idx++;
            }
            int last = dsu.H.size();
            dbg(ext[i - l]);
            for (const auto &j : ext[i - l]) {
                dsu.Union(u[j], v[j]);
            }
            ans[i] = sz[dsu.find(x[i])];
            dsu.roll(last);
        }
    }
    for (size_t i = 1; i <= q; i++) {
        if (ans[i] == -1)
            continue;
        cout << ans[i] << ln;
    }

    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/

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

bridges.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
bridges.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
bridges.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
bridges.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
bridges.cpp:85:20: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   85 |     DSU_roll(int _n) : n(_n), c(_n) {
      |                    ^
bridges.cpp:85:20: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:85:20: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:85:20: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:91:15: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   91 |     void init() {
      |               ^
bridges.cpp:91:15: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:91:15: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:91:15: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:99:19: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   99 |     int find(int v) {
      |                   ^
bridges.cpp:99:19: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:99:19: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:99:19: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:105:28: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  105 |     char Union(int v, int u) {
      |                            ^
bridges.cpp:105:28: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:105:28: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:105:28: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:118:20: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  118 |     void roll(int x) {
      |                    ^
bridges.cpp:118:20: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:118:20: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:118:20: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:129:21: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  129 | inline void systemd() {
      |                     ^
bridges.cpp:129:21: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:129:21: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:129:21: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:132:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  132 | char solve() {
      |            ^
bridges.cpp:132:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:132:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:132:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp: In function 'char solve()':
bridges.cpp:177:56: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  177 |         sort(ask.begin(), ask.end(), [&](int &l, int &r) {
      |                                                        ^
bridges.cpp:177:56: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:177:56: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:177:56: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp:180:68: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  180 |         sort(unchanged.begin(), unchanged.end(), [&](int &l, int &r) {
      |                                                                    ^
bridges.cpp:180:68: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:180:68: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:180:68: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bridges.cpp: At global scope:
bridges.cpp:210:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  210 | signed main() {
      |             ^
bridges.cpp:210:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bridges.cpp:210:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bridges.cpp:210:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• 서브태스크 1: 13 / 13
• 서브태스크 2: 16 / 16
• 서브태스크 3: 17 / 17
• 서브태스크 4: 14 / 14
• 서브태스크 5: 13 / 13
• 서브태스크 6: 27 / 27