QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#329983 | #185. Bridges | junbin | 0 | 1274ms | 10824kb | C++14 | 5.0kb | 2024-02-17 10:16:45 | 2024-02-17 10:16:47 |
Judging History
answer
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include<fstream>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define P pair
#define V vector
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FFOR(i, a, b) for (int i = a; i <= b; ++i)
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;}
out << "]";
return out;
}
const int N = 200000 + 10;
int ans[N], L[2010], R[2010], timing[N];
bool vis1[N], vis2[N];
vector<int> T[2010];
struct E {
int u, v, w, t, i;
} e[N], ee[N];
struct Q {
int u, w, t, i;
bool operator< (const Q& other) {
return w > other.w;
}
} q[N];
bool comp1(E& e1, E& e2) {
return e1.t < e2.t;
}
bool comp2(E& e1, E& e2) {
return e1.w > e2.w;
}
//DSU
struct Node {
int fax, fay, w, sz;
} stk[N];
int p[N], rk[N], sz[N];
int top = 0;
int find(int x) {
return p[x] == x ? x : find(p[x]);
}
bool merge(int u, int v) {
int fax = find(u), fay = find(v);
if(rk[fax] > rk[fay]) {
swap(fax, fay);
}
//注意这里,否则树的高度会不一样而导致TLE
if(fax != fay) {
stk[top++] = (Node){fax, fay, (rk[fax] == rk[fay]), sz[fay]};
p[fax] = fay;
sz[fay] += sz[fax];
if(rk[fay] == rk[fax]) rk[fay]++;
return true;
}
return false;
}
void undo() {
while(top > 0) {
top--;
int fax = stk[top].fax, fay = stk[top].fay;
p[fax] = fax;
rk[fay] -= stk[top].w;
sz[fay] = stk[top].sz;
}
}
////////////////////////////////////////////////////////////////////
void init(int n, int m) {
top = 0;
for(int i = 0; i <= n; i++) {
p[i] = i, sz[i] = 1, rk[i] = 0;
}
for(int i = 0; i <= m; i++) vis1[i] = false;
}
int cnt = 0;
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
e[i].t = 0;
e[i].i = i;
}
int k = 0, ti = 0, o = 0;
scanf("%d", &o);
for(int i = 0; i < o; i++) {
int op;
scanf("%d", &op);
if(op == 1) {
int ith, w;
scanf("%d%d", &ith, &w);
e[m] = {e[ith - 1].u, e[ith - 1].v, w, ++ti, ith - 1};
m++;
} else {
scanf("%d%d", &q[k].u, &q[k].w);
q[k].t = ++ti;
q[k].i = k;
k++;
}
}
for(int i = 0; i < m; i++) {
ee[i] = {e[i].u, e[i].v, e[i].w, e[i].t, e[i].i};
}
sort(e, e + m, comp1); //按w 从大到小排序
sort(q, q + k); //按t 从小到大排序
//分块范围初始化
int s = sqrt(m);
int t = 0;
for(int i = 0; i < m; i += s) {
L[t] = i;
R[t] = min(m - 1, i + s - 1);
t++;
}
//分块分配处理
for(int i = 0; i < k; i++) {
int j = 0;
while(j < t && e[R[j]].t <= q[i].t) j++;
T[min(j, t - 1)].push_back(i);
}
//for(int i = 0; i < t; i++) cout << i << " " << T[i] << endl;
for(int i = 0; i < t; i++) {
int l = L[i], r = R[i];
init(n, m);
sort(e, e + l, comp2);
cout << endl;
for(int o = l; o <= r; o++) {
vis1[e[o].i] = true;
}
vector<E> cur;
int j = 0;
for(int& x : T[i]) {
int u = q[x].u, w = q[x].w, idx = q[x].i;
while(j < l && e[j].w >= w) {
if(e[j].w != ee[e[j].i].w) { //not the newest
} else {
if(vis1[e[j].i]) {
cur.push_back(e[j]);
} else {
merge(e[j].u, e[j].v);
}
}
j++;
}
top = 0;
for(int o = r; o >= l; o--) {
if(e[o].t <= q[x].t) {
if(!vis2[e[o].i]) {
if(e[o].w >= w) {
merge(e[o].u, e[o].v);
}
}
vis2[e[o].i] = true;
}
}
for(int o = cur.size() - 1; o >= 0; o--) {
if(cur[o].t <= q[x].t) {
if(!vis2[cur[o].i]) {
if(cur[o].w >= w) {
merge(cur[o].u, cur[o].v);
}
}
vis2[cur[o].i] = true;
}
}
for(int o = l; o <= r; o++) vis2[e[o].i] = false;
ans[idx] = sz[find(u)];
undo();
}
for(int o = l; o <= r; o++) { //update edge with the newest info
ee[e[o].i].w = e[o].w;
}
}
for(int i = 0; i < k; i++) {
printf("%d\n", ans[i] == 0 ? 1 : ans[i]);
}
}
int main() {
int t = 1;
while(t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3876kb
input:
3 4 1 2 5 2 3 2 3 1 4 2 3 8 5 2 1 5 1 4 1 2 2 5 1 1 1 2 3 2
output:
3 2 3
result:
wrong answer 1st lines differ - expected: '3', found: ''
Subtask #2:
score: 0
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 1274ms
memory: 9956kb
input:
50000 49999 1 2 976392398 2 3 773336157 3 4 849545817 4 5 194340376 5 6 386778507 6 7 40561907 7 8 260116638 8 9 85673124 9 10 149683208 10 11 724746156 11 12 155084527 12 13 416939763 13 14 753621724 14 15 384948880 15 16 625917615 16 17 833747431 17 18 764302034 18 19 4518648 19 20 405679793 20 21...
output:
...
result:
wrong answer 1st lines differ - expected: '7', found: ''
Subtask #3:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 981ms
memory: 9032kb
input:
32767 32766 1 2 152523690 1 3 736211233 2 4 163158345 2 5 200010458 3 6 902682843 3 7 427399287 4 8 770411775 4 9 322256303 5 10 252775416 5 11 346597970 6 12 297314023 6 13 727299741 7 14 985621564 7 15 101953231 8 16 405434218 8 17 421655547 9 18 817411034 9 19 310455840 10 20 355126049 10 21 7038...
output:
1 1 2 2 6 6...
result:
wrong answer 1st lines differ - expected: '1', found: ''
Subtask #4:
score: 0
Wrong Answer
Test #45:
score: 0
Wrong Answer
time: 945ms
memory: 10824kb
input:
50000 100000 35231 1616 822934828 1668 2202 768458723 26049 41810 238904165 15936 42751 466996423 41068 21425 588205829 29502 11760 732391267 13029 44741 930695124 46168 22085 155239713 9505 43779 638894800 18665 43842 298794735 41763 15511 727702105 7865 27776 53447691 32904 34081 844499614 26327 9...
output:
...
result:
wrong answer 1st lines differ - expected: '2', found: ''
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%