이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
struct Info
{
int a, sza, ha;
int b, szb, hb;
};
struct Dsu
{
int n;
vector<int> t, sz, h;
vector<Info> histo;
void init(int nn)
{
histo.clear();
t.clear();
h.clear();
sz.clear();
n = nn;
t.resize(n);
iota(t.begin(), t.end(), 0);
sz.resize(n, 1);
h.resize(n, 0);
}
int root(int a)
{
while (a != t[a]) a = t[a];
return a;
}
bool join(int a, int b)
{
a = root(a);
b = root(b);
histo.push_back({ a, sz[a], h[a], b, sz[b], h[b] });
if (a == b) return 0;
if (h[a] < h[b]) swap(a, b);
t[b] = a;
h[a] += (h[a] == h[b]);
sz[a] += sz[b];
return 1;
}
void revert()
{
Info info = histo.back();
histo.pop_back();
int a = info.a, sza = info.sza, ha = info.ha;
int b = info.b, szb = info.szb, hb = info.hb;
t[a] = a;
sz[a] = sza;
h[a] = ha;
t[b] = b;
sz[b] = szb;
h[b] = hb;
}
};
struct Edge
{
int a, b, c;
};
signed main()
{
#ifdef ONPC
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int n, m, q;
cin >> n >> m;
map<int, int> mp;
vector<Edge> edges(m);
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
edges[i] = { a, b, c };
mp[c] = 0;
}
cin >> q;
vector<vector<int>> queries(q);
for (auto& query : queries)
{
int type;
cin >> type;
if (type == 1)
{
int id, nwc;
cin >> id >> nwc;
id--;
query = { type, id, nwc };
mp[nwc] = 0;
}
else
{
int vertex, weight;
cin >> vertex >> weight;
vertex--;
query = { 2, vertex, weight };
mp[weight] = 0;
}
}
int y = 0;
for (auto& it : mp)
{
it.second = y++;
}
for (int i = 0; i < m; i++)
{
edges[i].c = mp[edges[i].c];
}
for (auto& query : queries)
{
query[2] = mp[query[2]];
}
vector<vector<int>> cine(y);
for (int i = 0; i < m; i++)
{
cine[edges[i].c].push_back(i);
}
for (auto& query : queries)
{
int type = query[0];
if (type == 1)
{
int id = query[1], nwc = query[2];
cine[nwc].push_back(id);
}
}
vector<int> initial(m);
vector<int> what(q);
vector<vector<int>> intrebari(y);
const int Magic = 1000;
int low = 0;
while (low < q)
{
int high = min(q - 1, low + Magic - 1);
vector<bool> atins(m, 0);
for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 1) atins[queries[iq][1]] = 1;
for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 2) intrebari[queries[iq][2]].push_back(iq);
vector<int> speciale;
for (int i = 0; i < m; i++) if (atins[i]) speciale.push_back(i);
for (int i = 0; i < m; i++) initial[i] = edges[i].c;
Dsu dsu;
dsu.init(n);
for (int c = y - 1; c >= 0; c--)
{
for (auto& i : cine[c])
{
if (edges[i].c == c && !atins[i])
{
dsu.join(edges[i].a, edges[i].b);
}
}
for (auto& iq : intrebari[c])
{
int init_dim = (int)dsu.histo.size();
for (auto& i : speciale) edges[i].c = initial[i];
for (int iq2 = low; iq2 < iq; iq2++)
{
auto& query = queries[iq2];
int type = query[0];
if (type == 1)
{
int id = query[1], nwc = query[2];
edges[id].c = nwc;
}
}
int vertex = queries[iq][1], weight = queries[iq][2];
for (auto& i : speciale)
{
if (edges[i].c >= c)
{
dsu.join(edges[i].a, edges[i].b);
}
}
what[iq] = dsu.sz[dsu.root(vertex)];
while ((int)dsu.histo.size() > init_dim) dsu.revert();
}
}
for (int iq = low; iq <= high; iq++)
{
auto& query = queries[iq];
int type = query[0];
if (type == 1)
{
int id = query[1], nwc = query[2];
edges[id].c = nwc;
}
}
for (int iq = low; iq <= high; iq++) if (queries[iq][0] == 2) intrebari[queries[iq][2]].clear();
low = high + 1;
}
for (int iq = 0; iq < q; iq++)
{
if (queries[iq][0] == 2)
{
cout << what[iq] << "\n";
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'int main()':
bridges.cpp:204:34: warning: unused variable 'weight' [-Wunused-variable]
204 | int vertex = queries[iq][1], weight = queries[iq][2];
| ^~~~~~
# | 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... |