제출 #1136011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136011		nathan4690	다리 (APIO19_bridges)	C++20	100 / 100	1487 ms	142336 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const int maxn = 1e6+5, inf=1e9, bsz = 320;

struct DSU{
    int n;
    vector<int> p,sz;
    vector<pair<int&, int>> roll;
    DSU(){};
    DSU(int n): n(n), p(n+1, 0), sz(n+1, 1){
        f1(i,n) p[i] = i;
    }
    int find_set(int u){
        return (u == p[u] ? u : find_set(p[u]));
    }
    void union_set(int u, int v){
        u = find_set(u);
        v = find_set(v);
        if(sz[u] < sz[v]) swap(u, v);
        roll.push_back({p[v], p[v]});
        roll.push_back({sz[u], sz[u]});
        if(u == v) return;
        p[v] = u;
        sz[u] += sz[v];
    }
    void rollback(){
        roll.back().first = roll.back().second;
        roll.pop_back();
        roll.back().first = roll.back().second;
        roll.pop_back();
    }
};

struct Edge{
    int u, v, w, idx;
    Edge(int u = 0, int v = 0, int w = 0, int idx = 0): u(u), v(v), w(w), idx(idx){};
    bool operator<(const Edge &rhs) const{
        return w > rhs.w;
    }
};

struct Query{
    int tp, u, w;
};

int n, m, q, ans[maxn];
Edge e[maxn], ne[maxn];
Query qu[maxn];
vector<int> ie, car;
int mark[maxn];
vector<pair<int,int>> squ[maxn];
vector<int> wei[maxn];
DSU dsu;
vector<Edge> pree, nxte;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m;
    f1(i,m){
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].idx = i;
        ne[i] = e[i];
    }
    cin >> q;
    sort(ne+1,ne+m+1);
    f1(i,q) {
        cin >> qu[i].tp >> qu[i].u >> qu[i].w;
//        if(qu[i].tp == 2) swap(qu[i].u, qu[i].w);
    }
//    f1(i,m) cout << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';
    for(int l=1;l<=q;l+=bsz){
        int r = min(q, l + bsz - 1);
        ie.clear(); car.clear();
        for(int i=l;i<=r;i++){
            if(qu[i].tp == 1){
                ie.push_back(qu[i].u);
                mark[qu[i].u] = e[qu[i].u].w;
            }
        }
        sort(ie.begin(), ie.end());
        ie.resize(unique(ie.begin(), ie.end()) - ie.begin());
        for(int i=l;i<=r;i++){
            if(qu[i].tp == 1){
                mark[qu[i].u] = qu[i].w;
            }else{
                int idx = upper_bound(ne+1,ne+m+1,Edge(0, 0, qu[i].w)) - ne;
//                cout << i << " " << idx << '\n';
//                car.push_back(idx);
                squ[idx].push_back({qu[i].u, i});
                for(int u: ie){
                    wei[i].push_back(mark[u]);
                }
            }
        }
        dsu = DSU(n);
        f1(i, m+1){
            for(pair<int,int> qq: squ[i]){
                int u = qq.first, idx = qq.second, cnt = 0;
//                cout << u << ' ' << idx << endl;
                for(int j=0;j<ie.size();j++){
                    int ei = ie[j], ew = wei[idx][j];
                    if(ew >= qu[idx].w){
                        dsu.union_set(e[ei].u, e[ei].v);
                        cnt++;
                    }
                }
                ans[idx] = dsu.sz[dsu.find_set(u)];
//                cout << "ok" << endl;
                while(cnt--) dsu.rollback();
            }
            if(i <= m && !mark[ne[i].idx]) dsu.union_set(ne[i].u, ne[i].v);
        }
        pree.clear();
        nxte.clear();
        f1(i, m){
            if(mark[ne[i].idx]){
                ne[i].w = mark[ne[i].idx];
                nxte.push_back(ne[i]);
            }else pree.push_back(ne[i]);
            if(mark[i]) e[i].w = mark[i];
            squ[i].clear();
        }
        f1(i,m) mark[i] = 0;
        sort(nxte.begin(), nxte.end());
        merge(pree.begin(), pree.end(), nxte.begin(), nxte.end(), ne+1);
        squ[m+1].clear();
        for(int i=l;i<=r;i++) wei[i].clear();
    }
    f1(i,q){
        if(qu[i].tp == 2) cout << ans[i] << '\n';
    }
    return 0;
}

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

bridges.cpp: In function 'int main()':
bridges.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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