# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
172443 | dndhk | 다리 (APIO19_bridges) | C++14 | 141 ms | 10596 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 50010;
const int MAX_Q = 100010;
int N, M, Q;
struct Edge{
int x, y, z;
bool operator <(const Edge &a)const{
return z<a.z;
}
};
vector<Edge> edge;
struct Query{
int t;
int x, y;
};
vector<Query> query;
struct Group{
int g[MAX_N+1];
int sz[MAX_N+1];
void ig(){
for(int i=1; i<=N; i++) {
g[i] = i;
sz[i] = 1;
}
}
int fg(int x){
return (x==g[x])?x:g[x] = fg(g[x]);
}
void ug(int x, int y){
x = fg(x); y = fg(y);
if(x==y) return;
if(sz[x]>sz[y]){
g[y] = x;
sz[x]+=sz[y];
}else{
g[x] = y;
sz[y]+=sz[x];
}
}
} G;
void pro1(){
for(int i=1; i<=Q; i++){
int t; scanf("%d", &t);
int a, b;
if(t==1){
scanf("%d%d", &a, &b);
edge[a].z = b;
}else{
scanf("%d%d", &a, &b);
G.ig();
for(int j=1; j<=M; j++){
if(edge[j].z<b) continue;
G.ug(edge[j].x, edge[j].y);
}
int ans = 0;
for(int j=1; j<=N; j++){
if(G.fg(j)==G.fg(a)) ans++;
}
printf("%d\n", ans);
}
}
}
struct ST{
int t, idx, x, y, z;
bool operator <(const ST &a)const{
if(z==a.z){
if(t==2) return true;
if(a.t==2) return false;
return x<a.x;
}return z<a.z;
}
};
vector<ST> vt;
int ans[MAX_Q+1];
void pro2(){
G.ig();
for(int i=1; i<=M; i++){
vt.pb({1, 0, edge[i].x, edge[i].y, edge[i].z});
}
for(int i=0; i<Q; i++){
vt.pb({2, i, query[i].x, 0, query[i].y});
}
sort(vt.begin(), vt.end());
while(!vt.empty()){
ST now = vt.back(); vt.pop_back();
if(now.t==1){
G.ug(now.x, now.y);
}else{
ans[now.idx] = G.sz[G.fg(now.x)];
}
}
for(int i=0; i<Q; i++){
printf("%d\n", ans[i]);
}
}
int main(){
scanf("%d%d", &N, &M);
edge.pb({0, 0, 0});
for(int i=1; i<=M; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edge.pb({a, b, c});
}
scanf("%d", &Q);
if(N<=1000 && M<=1000 && Q<=10000){
pro1();
return 0;
}
bool tf = true;
for(int i=1; i<=Q; i++){
int a, b, c; scanf("%d%d%d", &a, &b, &c);
if(a==1) tf = false;
query.pb({a, b, c});
}
if(tf){
pro2();
return 0;
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |