제출 #1299384

#제출 시각아이디문제언어결과실행 시간메모리
1299384adscoding다리 (APIO19_bridges)C++20
0 / 100
814 ms589824 KiB
#include <bits/stdc++.h>
#define time() cerr << " \n " << "Time : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms."
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define all(x) x.begin(), x.end()
#define uni(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) cerr << "[ " << #__VA_ARGS__ << " ] = ", debug(__VA_ARGS__)
template<typename T> void debug(T x) { cerr << x << "\n\n"; }
template<typename T, typename... Args> void debug(T x, Args... args) { cerr << x << " , ", debug(args...); }


// --------------------------------------------------------------------------------------------------------------------

const int maxn = 5e4 + 3;
const int maxM = 1e5 + 3;
const int B = 317;
int n, m, q, ans[maxM];

// --------------------------------------------------------------------------------------------------------------------

struct Ed
{
    int u, v, w, id;
    Ed() {}
    Ed(int u, int v, int w) : u(u), v(v), w(w) {}
};

struct Qr
{
    int op, x, y, id;
};

vector<Ed> Eds[503];
vector<Ed> EdsEle[maxM];

Ed Feds[maxM];
Qr qrs[maxM];
int lst[maxM];


void updRange(int l, int r, Ed ed)
{
    int bL = l / B, bR = r / B;
    FOR(i, bL + 1, bR - 1) Eds[i].push_back(ed);

    FOR(i, l, min(r, (bL + 1) * B - 1))
    {
        if (qrs[i].op != 2 || qrs[i].y > ed.w) continue;
        EdsEle[i].push_back(ed);
    }
    if (bL != bR) FOR(i, max(l, bR * B), r)
    {
        if (qrs[i].op != 2 || qrs[i].y > ed.w) continue;
        EdsEle[i].push_back(ed);
    }
}

bool cmpQ(const Qr &A, const Qr &B)
{
    return A.y > B.y;
}

struct DSU
{
    vector<int> e;
    vector<pair<int &, int>> history;
    void init() {e.assign(n + 3, -1);}
    int get(int u) {return e[u] < 0 ? u : get(e[u]);}
    bool unite(int u, int v)
    {
        u = get(u); v = get(v);
        if (u == v) return false;
        if (e[u] > e[v]) swap(u, v);
        history.push_back({e[u], e[u]});
        history.push_back({e[v], e[v]});
        e[u] += e[v];
        e[v] = u;
        return true;
    }

    int versions() {return (int)history.size();}

    void rollback(int until)
    {
        while (history.size() > until)
        {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }
} dsu;

void solve()
{
    cin >> n >> m;
    FOR( i, 1, m)
    {
        int u, v, w; cin >> u >> v >> w;
        if (u > v) swap(u, v);
        Feds[i].u = u;
        Feds[i].v = v;
        Feds[i].w = w;
        Feds[i].id = i;
    }

    qrs[0].op = 1;
    cin >> q;
    FOR(iq, 1, q)
    {
        cin >> qrs[iq].op >> qrs[iq].x >> qrs[iq].y;
        qrs[iq].id = iq;
        if (qrs[iq].op != 1) continue;
        updRange(lst[qrs[iq].x], iq - 1, Feds[qrs[iq].x]);

        lst[qrs[iq].x] = iq;
        Feds[qrs[iq].x].w = qrs[iq].y;
    }

    FOR(i, 1, m)
    {
        updRange(lst[i], q, Feds[i]);
    }

    dsu.init();

    FOR(bl, 0, q / B)
    {
        int sta = bl * B, ed = min(q, (bl + 1) * B - 1);
        if (sta > ed) break;

        vector<Qr> cur_qr;
        FOR(i, sta, ed)
        {
            if (qrs[i].op != 2) continue;
            cur_qr.push_back(qrs[i]);
        }

        sort(all(cur_qr), cmpQ);

        int ptr = 0;
        for (const Qr &Q : cur_qr)
        {
            int id = Q.id;
            while (ptr < Eds[bl].size() && Eds[bl][ptr].w >= Q.y)
            {
                dsu.unite(Eds[bl][ptr].u, Eds[bl][ptr].v);
                ++ptr;
            }

            int time = dsu.versions();

            for (const Ed ed : EdsEle[id])
            {
                dsu.unite(ed.u, ed.v);
            }
            ans[id] = -dsu.e[dsu.get(Q.x)];

            dsu.rollback(time);
        }
    }

    FOR(i, 1, q) if (qrs[i].op == 2) cout << ans[i] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "test"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    time();
    return 0;
}

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

bridges.cpp: In function 'int main()':
bridges.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...