제출 #568764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568764		shrimb	다리 (APIO19_bridges)	C++17	43 / 100	606 ms	21788 KiB

bridges

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 100001;
const int N = exp2(ceil(log2(maxn)));

vector<pair<int,int>> adj[maxn];
array<int, 3> E[maxn];
int w[maxn];

int dsu[maxn];
int sz[maxn];

int Find (int x) {
    return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
    int x = Find(a), y = Find(b);
    if (x==y) return;
    sz[y] += sz[x];
    dsu[x] = y;
}

int seg[2 * N];
int Left, Right, Pos, Val;

int Combine (int a, int b) {
    return min(a, b);
}

int Query (int l = 1, int r = N, int ind = 1) {
    if (l > Right || r < Left) return INT_MAX ;
    if (l >= Left and r <= Right) return seg[ind];
    int m = (l + r) / 2;
    return Combine(Query(l, m, ind * 2), Query(m + 1, r, ind * 2 + 1));
}

void Update () {
    int ind = N + Pos - 1;
    seg[ind] = Val;
    while (ind /= 2) seg[ind] = Combine(seg[ind * 2], seg[ind * 2 + 1]);
}

bool cmp (array<int, 4> &a, array<int, 4> &b) {
    return a[2] > b[2];
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    bool LINE = (m == n - 1);

    for (int i = 0 ; i < m ; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        adj[u].emplace_back(v, i + 1);
        adj[v].emplace_back(u, i + 1);
        E[i] = {x, u, v};
        seg[N + i] = x;
        LINE &= (u == i + 1 and v == i + 2);
        w[i + 1] = x;
    }

    for (int i = N - 1 ; i ; i--) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }

    int q;
    cin >> q;
    // if(0)
    if (LINE) {
        // assert(0);
        while (q--) {
            int t;
            cin >> t;
            if (t == 1) {
                cin >> Pos >> Val;
                Update();
            } else {
                int i, wj;
                cin >> i >> wj;
                // {i...m}
                // {1...i-1}
                int left, right;
                {
                    int l = i, r = m + 1;
                    while (r - l > 1) {
                        int m = (l + r) / 2;
                        Left=  i, Right = m;
                        if (Query() >= wj) l = m;
                        else r = m;
                    }
                    right = l;
                }
                {
                    int l = 0, r = i - 1;
                    while (r - l > 1) {
                        int m = (l + r) / 2;
                        Left = m, Right = i-1;
                        if (Query() >= wj) r = m;
                        else l = m;
                    }
                    left = r;
                }
                if (i == 1 || seg[N + i - 2] < wj) left++;
                if (i == n || seg[N + i - 1] < wj) right--;
                // cerr << left << " " << right << endl;
                cout << right - left + 2 << endl;
            }
        }
        return 0;
    }

    // if(0)
    if (n <= 1000 and m <= 1000 and q <= 10000) {
        while (q--) {
            int t;
            cin >> t;
            if (t == 1) {
                int b, r;
                cin >> b >> r;
                w[b] = r;
            } else {
                int s, wj;
                cin >> s >> wj;
                for (int i = 1 ; i <= n ; i++) dsu[i] = i, sz[i] = 1;
                for (int i = 1 ; i <= n ; i++) for (auto [j, b] : adj[i]) if (w[b] >= wj) Union(i, j);
                cout << sz[Find(s)] << endl;
            }
        }
        return 0;
    }

    array<int, 4> Q[q];

    bool tj2 = 1;

    for (int i = 0 ; i < q ; i++) {
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
        Q[i][3] = i;
        if (Q[i][0] == 1) tj2 = 0;
    }

    if (tj2) {
        int ans[q];
        for (int i = 1 ; i <= n ; i++) dsu[i] = i, sz[i] = 1;
        sort(Q, Q + q, cmp);
        sort(E, E + m);
        reverse(E, E + m);
        int j = 0;
        for (int i = 0 ; i < m ; i++) {
            while (j < q and E[i][0] < Q[j][2]) {
                ans[Q[j][3]] = sz[Find(Q[j][1])];
                j++;
            }
            Union(E[i][1], E[i][2]);
        }
        while (j < q) {
            ans[Q[j][3]] = sz[Find(Q[j][1])];
            j++;
        }
        for (int i = 0 ; i < q ; i++) cout << ans[i] << endl;
        return 0;
    }

}

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

bridges.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27