| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 133138 | rajarshi_basu | 다리 (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector
using namespace std;
const int MAXN = 50*1000+1;
const int MAXM = 2*MAXN;
struct DSU{
int parent[MAXN];
int sz[MAXN];
int rnk[MAXN];
void init(){
FOR(i,MAXN)parent[i] = i;
FOR(i,MAXN)sz[i] = 1;
FOR(i,MAXN)rnk[i] = 1;
}
int find(int a){
if(a == parent[a])return a;
return find(parent[a]);
}
void merge(int a,int b){
if(isSame(a,b))return;
int pa = find(a);
int pb = find(b);
sz[pa] += sz[pb];
parent[pb] = pa;
}
int getSize(int a){
return sz[find(a)];
}
bool isSame(int a,int b){
return find(a) == find(b);
}
};
struct edge{
int ID;
int a,b;
int w;
edge(int id,int aa,int bb,int ww){
ID = id;
a = aa;
b = bb;
w = ww;
}
};
struct query{
int type; // 1 is update, 2 is query
int tm;
int info1; // node for query, edge for update
int info2; // value for either
int id;
query(int t,int a,int b,int c){
type = t;
tm = id = a;
info1 = b;
info2 = c;
}
};
int finalANS[MAXM];
vv<edge> allEdges;
vi rem;
bool edg[MAXM];
void processQueries(vv<query> allQueries){
FOR(i,MAXM)edg[i] = 0;
for(auto e : allQueries){
if(e.type == 1){
edg[e.info1] = 1;
rem.pb(e.info1);
}
}
//cout << "REM CONTENTS : " ;
//for(auto e : rem)cout << e << " ";cout << endl;
//DSU dsu;
//dsu.init();
vv<query> actualQueries;
for(auto e : allQueries){
if(e.type == 2){
actualQueries.pb(e);
}
}
sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){
return a.info2 >= b.info2;
});
for(auto q : actualQueries){
//cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl;
DSU dsu;
dsu.init();
FOR(i,allEdges.size()){
if(edg[i])continue;
if(allEdges[i].w < q.info2)continue;
//cout << "PERMEDGE PROCESSED : " << i+1 << endl;
dsu.merge(allEdges[i].a,allEdges[i].b);
}
map<int,int> mp;
for(auto xx : rem){
mp[xx] = allEdges[xx].w;
}
for(auto e : allQueries){
if(e.type == 2)continue;
if(e.tm > q.tm)continue;
//cout << "BLOCK EDGE SEEN : " << e.info1+1 << " " << e.info2 << endl;
mp[e.info1] = e.info2;
}
for(auto x : mp){
if(x.ss >= q.info2){
//cout << "BLOCK EDGE SEEN : " << x.ff+1 << " " << x.ss << endl;
dsu.merge(allEdges[x.ff].a,allEdges[x.ff].b);
}
}
finalANS[q.id] = dsu.getSize(q.info1);
}
for(auto e : allQueries){
if(e.type == 1){
allEdges[e.info1] = e.info2;
}
}
}
bool quer[MAXM];
int main(){
int n,m;
cin >> n >> m;
FOR(i,m){
int a,b,c;
cin >> a >> b >> c;
a--;b--;
allEdges.pb(edge(i,a,b,c));
}
int q;
cin >> q;
FOR(i,MAXM)finalANS[i] = -1;
int BLOCK = 100;
vv<query> allq;
FOR(i,q){
int a,b,c;
cin >> a >> b >> c;
if(a == 2)quer[i] = 1;
b--;
allq.pb(query(a,i,b,c));
if((i+1)%BLOCK == 0){
processQueries(allq);
allq.clear();
}
}
if(allq.size() > 0)processQueries(allq);
FOR(i,q){
if(quer[i])cout << finalANS[i] << endl;
}
return 0;
}