結果

問題 No.416 旅行会社
ユーザー Hachimori
提出日時 2016-08-26 23:11:40
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 633 ms / 4,000 ms
コード長 3,006 bytes
コンパイル時間 1,056 ms
コンパイル使用メモリ 79,596 KB
実行使用メモリ 15,468 KB
最終ジャッジ日時 2024-12-14 19:49:33
合計ジャッジ時間 8,255 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<set>
#define bgnE first
#define endE second
using namespace std;
const int BUF = 100005;
typedef pair<int, int> Edge;
class DisjointSet {
private:
int node2group[BUF];
vector<vector<int> > group2node;
public:
DisjointSet() {}
DisjointSet(int n) {
group2node = vector< vector<int> >(n);
for (int i = 0; i < n; ++i) {
node2group[i] = i;
group2node[i].push_back(i);
}
}
void merge(int a, int b) {
if (find(a) != find(b)) {
vector<int> &groupA = findGroup(a);
vector<int> &groupB = findGroup(b);
if (groupA.size() < groupB.size()) {
while (!groupA.empty()) {
groupB.push_back(groupA.back());
groupA.pop_back();
}
node2group[find(a)] = find(b);
}
else {
while (!groupB.empty()) {
groupA.push_back(groupB.back());
groupB.pop_back();
}
node2group[find(b)] = find(a);
}
}
}
int find(int a) {
if (node2group[a] == a) return a;
return node2group[a] = find(node2group[a]);
}
vector<int>& findGroup(int a) {
return group2node[find(a)];
}
};
int nNode;
set<Edge> availEdges;
vector<Edge> removeEdgeOrder;
void read() {
availEdges.clear();
removeEdgeOrder.clear();
int nEdge, nQuery;
cin >> nNode >> nEdge >> nQuery;
for (int i = 0; i < nEdge; ++i) {
int s, t;
cin >> s >> t;
--s;
--t;
availEdges.insert(Edge(s, t));
}
for (int i = 0; i < nQuery; ++i) {
int s, t;
cin >> s >> t;
--s;
--t;
availEdges.erase(Edge(s, t));
removeEdgeOrder.push_back(Edge(s, t));
}
}
void work() {
static DisjointSet dset;
dset = DisjointSet(nNode);
for (set<Edge>::iterator it = availEdges.begin(); it != availEdges.end(); ++it) {
Edge edge = *it;
dset.merge(edge.bgnE, edge.endE);
}
static int ans[BUF];
for (int i = 0; i < nNode; ++i) {
if (dset.find(0) == dset.find(i)) {
ans[i] = -1;
}
}
for (int i = removeEdgeOrder.size() - 1; i >= 0; --i) {
Edge &addEdge = removeEdgeOrder[i];
if (dset.find(0) == dset.find(addEdge.endE)) {
swap(addEdge.bgnE, addEdge.endE);
}
if (dset.find(0) == dset.find(addEdge.bgnE) && dset.find(0) != dset.find(addEdge.endE)) {
vector<int> &joinedGroup = dset.findGroup(addEdge.endE);
for (int j = 0; j < joinedGroup.size(); ++j) {
ans[joinedGroup[j]] = i + 1;
}
}
dset.merge(addEdge.bgnE, addEdge.endE);
}
for (int i = 1; i < nNode; ++i) {
cout << ans[i] << endl;
}
}
int main() {
read();
work();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0