# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
258015 | BamiTorabi | 다리 (APIO19_bridges) | C++14 | 3099 ms | 14324 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Sasayego! Sasayego! Shinzou wo Sasageyo!
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x) cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
const int maxN = 1e5 + 5;
const int SQ = 1000;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
pair <int, pii> E[maxN], Q[maxN];
stack <int> st;
int par[maxN], sz[maxN];
int change[maxN], wt[maxN], ans[maxN];
vector <int> vec, Eix[maxN], Qix[maxN], tmp;
int getpar(int v, bool flag = false){
if (!flag)
return (par[v] == v ? v : par[v] = getpar(par[v], flag));
while (par[v] != v)
v = par[v];
return v;
}
void join(int u, int v, bool flag = false){
u = getpar(u, flag);
v = getpar(v, flag);
if (u == v){
if (flag)
st.push(-1);
return;
}
if (sz[u] < sz[v])
swap(u, v);
if (flag)
st.push(v);
par[v] = u;
sz[u] += sz[v];
return;
}
void undo(){
int v = st.top(); st.pop();
if (v == -1)
return;
int u = par[v];
sz[u] -= sz[v];
par[v] = v;
return;
}
int main(){
time_t START = clock();
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &E[i].second.second, &E[i].second.first, &E[i].first);
int q; scanf("%d", &q);
for (int i = 0; i < q; i++){
scanf("%d%d%d", &Q[i].first, &Q[i].second.second, &Q[i].second.first);
if (Q[i].first == 2)
vec.push_back(Q[i].second.first);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for (int i = 1; i <= m; i++)
E[i].first = upper_bound(vec.begin(), vec.end(), E[i].first) - vec.begin() - 1;
for (int i = 0; i < q; i++)
Q[i].second.first = upper_bound(vec.begin(), vec.end(), Q[i].second.first) - vec.begin() - 1;
for (int id = 0, ss = SQ; id < q; id += ss){
ss = min(ss, q - id);
for (int i = 1; i <= m; i++)
change[i] = false;
for (int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
for (int i = id; i < id + ss; i++){
if (Q[i].first == 1)
change[Q[i].second.second] = true;
else
Qix[Q[i].second.first].push_back(i);
}
for (int i = 1; i <= m; i++)
(change[i] ? tmp.push_back(i) : Eix[E[i].first].push_back(i));
sort(tmp.begin(), tmp.end());
for (int i = (int)vec.size(); i > -1; i--){
for (int e : Eix[i])
join(E[e].second.second, E[e].second.first);
for (int x : Qix[i]){
for (int e : tmp)
wt[e] = E[e].first;
for (int j = id; j < x; j++)
if (Q[j].first == 1)
wt[Q[j].second.second] = Q[j].second.first;
for (int e : tmp)
if (wt[e] >= i)
join(E[e].second.second, E[e].second.first, 1);
ans[x] = sz[getpar(Q[x].second.second, 1)];
while (!st.empty())
undo();
}
Eix[i].clear();
Qix[i].clear();
}
for (int i = id; i < id + ss; i++){
if (Q[i].first == 1)
E[Q[i].second.second].first = Q[i].second.first;
else
printf("%d\n", ans[i]);
}
}
time_t FINISH = clock();
cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " millisecond.seconds.\n";
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... |