Submission #681579

#	Time	Username	Problem	Language	Result	Execution time	Memory
681579		79brue	Bridges (APIO19_bridges)	C++17	100 / 100	2685 ms	11120 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int G = 320;

struct UnionFind{
    int n;
    int par[50002], sz[50002];
    vector<pair<int, int> > stk;

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;
        stk.clear();
    }

    int find(int x){
        if(par[x] == x) return x;
        return find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x==y) return;
        if(sz[x] > sz[y]) swap(x, y);
        stk.push_back(make_pair(-y, sz[y]));
        stk.push_back(make_pair(x, par[x]));
        par[x] = y;
        sz[y] += sz[x];
    }

    void rollback(){
        while(!stk.empty()){
            auto p = stk.back();
            stk.pop_back();
            if(p.first < 0) sz[-p.first] = p.second;
            else            par[p.first] = p.second;
        }
    }

    void check(){
        stk.clear();
    }
} dsu;

struct Edge{
    int x, y, w, idx;
    Edge(int x, int y, int w, int idx): x(x), y(y), w(w), idx(idx){}
    bool operator<(const Edge &r)const{
        return w>r.w;
    }
};

int n, m, q;
vector<Edge> edgeVec;
int ex[100002], ey[100002], weight[100002];
int qt[100002], qa[100002], qb[100002];
int ans[100002];

void solve(int L, int R);

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        ex[i] = x, ey[i] = y, weight[i] = w;
        edgeVec.push_back(Edge(x, y, w, i));
    }
    sort(edgeVec.begin(), edgeVec.end());

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d %d", &qt[i], &qa[i], &qb[i]);
    }

    for(int d=1; d<=q; d+=G){
        solve(d, min(q, d+G-1));
    }
    for(int i=1; i<=q; i++) if(qt[i]==2) printf("%d\n", ans[i]);
}

bool edgeUsed[100002];

struct dat{
    int x, w, idx;
    dat(){}
    dat(int x, int w, int idx): x(x), w(w), idx(idx){}
    bool operator<(const dat &r)const{
        return w>r.w;
    }
};

int edgeIdx[100002];
int matrix[500][500]; /// matrix[i][j]: i번 간선의 쿼리 시점 j에서의 가중치
vector<int> usedEdges;
int S;

void solve(int L, int R){ /// L~R번 쿼리를 처리
    for(auto &p: edgeVec) p.w = weight[p.idx];
    sort(edgeVec.begin(), edgeVec.end());

    vector<dat> queryVec;
    usedEdges.clear();
    for(int i=L; i<=R; i++){
        if(qt[i] == 1) edgeUsed[qa[i]] = 1, usedEdges.push_back(qa[i]);
        else queryVec.push_back(dat(qa[i], qb[i], i));
    }
    sort(queryVec.begin(), queryVec.end());

    dsu.init(n);

    /// matrix를 채우고 각 시점에서 가중치에 대한 정보를 얻자
    sort(usedEdges.begin(), usedEdges.end());
    usedEdges.erase(unique(usedEdges.begin(), usedEdges.end()), usedEdges.end());
    S = (int)usedEdges.size();

    for(int i=0; i<S; i++){
        int x = usedEdges[i];
        edgeIdx[x] = i;
        matrix[i][0] = weight[x];
        for(int j=L; j<=R; j++){
            if(qt[j] == 1 && qa[j] == x) matrix[i][j-L] = qb[j];
            else if(j>L) matrix[i][j-L] = matrix[i][j-L-1];
        }
    }

    int pnt = 0;
    for(dat p: queryVec){
        while(pnt < (int)edgeVec.size() && edgeVec[pnt].w >= p.w){
            if(!edgeUsed[edgeVec[pnt].idx]) dsu.merge(edgeVec[pnt].x, edgeVec[pnt].y);
            pnt++;
        }
        dsu.check();

        for(int e: usedEdges){
            if(matrix[edgeIdx[e]][p.idx-L] < p.w) continue;
            dsu.merge(ex[e], ey[e]);
        }
        ans[p.idx] = dsu.sz[dsu.find(p.x)];

        dsu.rollback();
    }

    /// weight 배열 업데이트
    for(int i=L; i<=R; i++) if(qt[i] == 1) weight[qa[i]] = qb[i], edgeUsed[qa[i]] = 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d %d", &x, &y, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d %d %d", &qt[i], &qa[i], &qb[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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