結果
| 問題 |
No.1054 Union add query
|
| コンテスト | |
| ユーザー |
 tarattata1
|
| 提出日時 | 2020-05-15 22:50:31 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,647 bytes |
| コンパイル時間 | 1,318 ms |
| コンパイル使用メモリ | 102,884 KB |
| 実行使用メモリ | 106,608 KB |
| 最終ジャッジ日時 | 2024-09-19 12:07:37 |
| 合計ジャッジ時間 | 6,196 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 7 WA * 1 |
ソースコード
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996)
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
//const long long MOD = 1000000007;
const long long MOD = 998244353;
using namespace std;
class UF
{
private:
int num;
vector<int> par;
vector<int> siz;
public:
//vector<int> val;
public:
UF(int n): num(n) {
par.resize(n);
siz.resize(n);
//val.resize(n);
int i;
for(i=0; i<n; i++) {
par[i]=i; siz[i]=1;
//val[i]=0;
}
}
int find(int x) {
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x=find(x);
y=find(y);
if(x==y) return;
if(siz[x]<siz[y]) {
par[x]=y;
siz[y]=siz[x]+siz[y];
//val[y]=val[x]+val[y];
}
else {
par[y]=x;
siz[x]=siz[x]+siz[y];
//val[x]=val[x]+val[y];
}
}
bool same(int x, int y) {
return find(x)==find(y);
}
int size(int x) {
return siz[find(x)];
}
int ngroup() {
//int ngroup( int& ans ) {
int count=0;
int i;
for(i=0; i<num; i++) {
if(par[i]==i) {
count++;
//ans += (val[i]? siz[i]: siz[i]-1);
}
}
return count;
}
};
vector<vector<int> > g;
vector<int> eu, bf, af;
void dfs(int par, int curr)
{
int cnt0=(int)eu.size();
eu.push_back(curr);
bf[curr] = cnt0;
int i;
for (i = 0; i < (int)g[curr].size(); i++) {
int next = g[curr][i];
if (par == next) continue;
dfs(curr, next);
}
af[curr] = (int)eu.size();
return;
}
const long long INF2 = (((ll)1<<31)-1);
template<class T> class SegTree // 0-indexed
{
private:
int n; // 葉の数
vector<T> data; // ノードの値を持つ配列
vector<T> lazy; // 遅延評価を持つ配列
T def; // 初期値かつ単位元
T operation(T a, T b) // 区間クエリで使う処理
{
//return min(a, b); // 区間minクエリ
return a+b; // 区間和クエリ
}
T update(T a, T b) // 点更新で使う処理
{
//return a+b; // 加算の場合
return b; // 更新の場合
}
void eval( int k, int l, int r ) // ノードkについて遅延評価を行う
{
if(lazy[k] != 0) {
data[k] += lazy[k];
if(r - l > 1) {
lazy[2*k+1] += lazy[k] / 2;
lazy[2*k+2] += lazy[k] / 2;
}
lazy[k] = 0;
}
return;
}
void _add(int a, int b, T x, int k, int l, int r) {
if(r < 0) r = n;
eval(k, l, r); // k 番目のノードに対して遅延評価を行う
if(b <= l || r <= a) return; // 範囲外なら何もしない
// 完全に被覆しているならば、遅延配列に値を入れた後に評価
if(a <= l && r <= b) {
lazy[k] += (r - l) * x;
eval(k, l, r);
}
// そうでないならば、子ノードの値を再帰的に計算して、
// 計算済みの値をもらってくる
else {
_add(a, b, x, 2*k+1, l, (l+r)/2);
_add(a, b, x, 2*k+2, (l+r)/2, r);
data[k] = data[2*k+1] + data[2*k+2];
}
}
// 区間[a,b)の総和。ノードk=[l,r)に着目している。
T _query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return def; // 交差しない
eval(k, l, r);
if (a <= l && r <= b)
return data[k]; // a,l,r,bの順で完全に含まれる
else {
T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
return operation(c1, c2);
}
}
public:
SegTree(int _n) { // _n:必要サイズ
//def = INF2; // 初期値かつ単位元（minのときINF2)
def = 0; // 初期値かつ単位元（和のとき0)
n = 1;
while (n < _n) n *= 2;
data = vector<T>(2 * n - 1, def);
lazy = vector<T>(2 * n - 1, 0);
}
// 場所i(0-indexed)の値をxで更新
void change(int i, T x) {
i += n - 1;
data[i] = update(data[i], x);
while (i > 0) {
i = (i - 1) / 2;
data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
}
}
// 区間更新
void add(int a, int b, T x) {
return _add(a, b, x, 0, 0, n);
}
// [a, b)の区間クエリを実行
T query(int a, int b) {
return _query(a, b, 0, 0, n);
}
// 添字でアクセス
T operator[](int i) {
return data[i + n - 1];
}
};
void solve()
{
int n, Q;
scanf("%d%d", &n, &Q);
vector<int> t(Q), a(Q), b(Q);
int cnt = 0;
int i;
for (i = 0; i < Q; i++) {
scanf("%d%d%d", &t[i], &a[i], &b[i]); a[i]--;
if(t[i]==1) b[i]--;
if (t[i] == 1) {
cnt++;
}
}
int num = cnt;
vector<int> mp(n+num);
for (i = 0; i < n + num; i++) mp[i] = i;
UF uf(n + num);
g.resize(n + num);
bf.resize(n + num);
af.resize(n + num);
cnt = 0;
for (i = 0; i < Q; i++) {
if (t[i] == 1) {
int aa = mp[uf.find(a[i])];
int bb = mp[uf.find(b[i])];
int id = n + cnt;
g[id].push_back(aa);
g[aa].push_back(id);
g[id].push_back(bb);
g[bb].push_back(id);
if (uf.same(aa, bb)) {
cnt++;
continue;
}
uf.unite(aa, bb);
uf.unite(aa, id);
int p = uf.find(aa);
mp[p] = id;
cnt++;
}
}
set<int> ss;
for (i = 0; i < n; i++) {
ss.insert(mp[uf.find(i)]);
}
auto it0 = ss.begin();
for (; it0 != ss.end(); ++it0) {
dfs(-1, *it0);
}
SegTree<ll> S(n + num);
UF uf2(n + num);
for (i = 0; i < n + num; i++) mp[i] = i;
cnt = 0;
for (i = 0; i < Q; i++) {
if (t[i] == 1) {
int aa = mp[uf2.find(a[i])];
int bb = mp[uf2.find(b[i])];
int id = n + cnt;
if (uf2.same(aa, bb)) {
cnt++;
continue;
}
uf2.unite(aa, bb);
uf2.unite(aa, id);
int p = uf2.find(aa);
mp[p] = id;
cnt++;
}
else if (t[i] == 2) {
int aa = mp[uf2.find(a[i])];
int t0 = bf[aa], t1 = af[aa];
S.add(t0, t1, b[i]);
}
else {
int aa = bf[a[i]];
ll ans=S.query(aa, aa+1);
printf("%lld\n", ans);
}
}
return;
}
int main(int argc, char* argv[])
{
#if 1
solve();
#else
int T;
scanf("%d", &T);
int t;
for(t=0; t<T; t++) {
//printf("Case #%d: ", t+1);
solve();
}
#endif
return 0;
}