# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
230760 | crackersamdjam | 다리 (APIO19_bridges) | C++14 | 3082 ms | 9064 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
using std::sort, std::vector, std::set, std::stack, std::pair, std::swap, std::min;
constexpr int MM = 1e5+5, SZ = 900;
int n, m, q, a[MM], b[MM], c[MM], ans[MM], par[MM], sz[MM];
struct st{
int op, i, w, id;
bool operator<(const st &o) const{
if(id/SZ == o.id/SZ)
return w > o.w;
return id/SZ < o.id/SZ;
}
} all[MM];
inline int find(int x){
while(x != par[x])
x = par[x];
return x;
}
stack<pair<int, int>> rm;
void merge(int x, int y, int keep){
x = find(x), y = find(y);
if(x == y)
return;
if(sz[x] > sz[y])
swap(x, y);
par[x] = y;
sz[y] += sz[x];
if(!keep)
rm.emplace(x, y);
}
void pop(){
while(rm.size()){
int x = rm.top().first, y = rm.top().second;
rm.pop();
par[x] = x;
sz[y] -= sz[x];
}
}
void reset(){
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
}
bool used[MM];
int main(){
memset(ans, -1, sizeof ans);
scan(n, m);
for(int i = 1; i <= m; i++){
scan(a[i], b[i], c[i]);
}
scan(q);
for(int i = 0; i < q; i++){
scan(all[i].op, all[i].i, all[i].w);
all[i].id = i;
}
sort(all, all+q);
for(int i = 0; i*SZ < q; i++){
int l = i*SZ, r = min(q, (i+1)*SZ);
reset();
vector<int> e, ord;
for(int j = l; j < r; j++){
if(all[j].op == 1){
used[all[j].i] = 1;
}
}
//loop edges (each one only once)
for(int j = 1; j <= m; j++){
if(used[j]){
//some
e.push_back(j);
}
else{
//all
ord.push_back(j);
}
}
sort(all(ord), [](int x, int y){
return c[x] < c[y];
});
vector<int> yes;
for(int j = l; j < r; j++)
yes.emplace_back(j);
sort(all(yes), [](int x, int y){
return all[x].id > all[y].id;
});
//already sorted by greatest w
for(int j = l; j < r; j++){
if(all[j].op == 2){
// all
while(ord.size() and c[ord.back()] >= all[j].w){
int id = ord.back(); ord.pop_back();
merge(a[id], b[id], 1);
}
//specific to this one
set<int> done;
for(int k: yes){
if(all[k].op == 1 and all[k].id < all[j].id){
int id = all[k].i;
if(!done.count(id) and all[k].w >= all[j].w){
merge(a[id], b[id], 0); //don't keep
}
done.insert(id);
}
}
// some
for(int k: e){
if(!done.count(k) and c[k] >= all[j].w){
merge(a[k], b[k], 0);
}
}
ans[all[j].id] = sz[find(all[j].i)];
pop();
}
}
reverse(all(yes));
for(int j: yes){
if(all[j].op == 1){
used[all[j].i] = 0;
c[all[j].i] = all[j].w;
//update for future batches
}
}
}
for(int i = 0; i < q; i++){
if(~ans[i])
print(ans[i]);
}
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... |