이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e5+5;
const int lim = 850;
const int maxs = lim+5;
int n, m, q;
int a[maxn], b[maxn], w[maxn];
bool chang[maxn];
struct que
{
int t, a, b, id;
bool operator < (que other)
{
return b> other.b;
}
};
que qq[maxn];
const int maxu = 5e4+5;
struct dsu
{
int par[maxu], rnk[maxu], cc[maxu];
struct hist
{
int u, rnku, ccu, v, rnkv, ccv;
hist(int _u, int _rnku, int _ccu, int _v, int _rnkv, int _ccv)
{
u = _u;
rnku = _rnku;
ccu = _ccu;
v = _v;
rnkv = _rnkv;
ccv = _ccv;
}
};
stack<hist> roll;
dsu(int n = 0)
{
for(int i = 1; i<= n; i++)
{
par[i] = i;
rnk[i] = 0;
cc[i] = 1;
}
}
int findset(int x)
{
if(x == par[x]) return x;
return findset(par[x]);
}
bool unite(int a, int b)
{
int u = findset(a), v = findset(b);
if(u == v) return false;
if(rnk[u]> rnk[v]) swap(u, v);
roll.push(hist(u, rnk[u], cc[u], v, rnk[v], cc[v]));
par[u] = v;
cc[v] += cc[u];
if(rnk[u] == rnk[v]) rnk[v]++;
return true;
}
void rollback()
{
hist k = roll.top(); roll.pop();
par[k.u] = k.u;
rnk[k.u] = k.rnku;
cc[k.u] = k.ccu;
par[k.v] = k.v;
rnk[k.v] = k.rnkv;
cc[k.v] = k.ccv;
}
};
dsu foo;
bool cmp(int a, int b)
{
return w[a]> w[b];
}
bool cmp2(que a, que b)
{
return a.id< b.id;
}
int ans[maxn];
int cap[maxn];
int st[4*maxn];
int ask(int i, int j, int p = 1, int L = 1, int R = n-1)
{
if(i> R || j< L) return 1e9;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = ask(i, j, 2*p, L, M);
int y = ask(i, j, 2*p+1, M+1, R);
return min(x, y);
}
void update(int x, int dx, int p = 1, int L = 1, int R = n-1)
{
if(x> R || x< L) return;
if(L == R)
{
st[p] = dx;
return;
}
int M = (L+R)/2;
update(x, dx, 2*p, L, M);
update(x, dx, 2*p+1, M+1, R);
st[p] = min(st[2*p], st[2*p+1]);
}
bool ok(int a, int b, int w)
{
return w<= ask(a, b-1);
}
void st2()
{
for(int i = 1; i<= m; i++)
{
update(i, w[i]);
}
scanf("%d", &q);
while(q--)
{
int t; scanf("%d", &t);
if(t == 1)
{
int id, c;
scanf("%d %d", &id, &c);
update(id, c);
}
else
{
int s, w; scanf("%d %d", &s, &w);
int lo = 1, hi = s;
while(lo< hi)
{
int mid = (lo+hi)/2;
if(ok(mid, s, w)) hi = mid;
else lo = mid+1;
}
int L = lo;
lo = s, hi = n;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
if(ok(s, mid, w)) lo = mid;
else hi = mid-1;
}
int R = lo;
printf("%d\n", R-L+1);
}
}
}
int deg[maxn];
void merge(vector<int> &res, vector<int> &A, vector<int> &B)
{
res.clear();
int n = A.size(), m = B.size();
int i = 0, j = 0;
while(i< n && j< m)
{
if(w[A[i]]> w[B[j]])
{
res.pb(A[i]);
i++;
}
else
{
res.pb(B[j]);
j++;
}
}
while(i< n)
{
res.pb(A[i++]);
}
while(j< m)
{
res.pb(B[j++]);
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i<= m; i++)
{
scanf("%d %d %d", &a[i], &b[i], &w[i]);
cap[i] = w[i];
deg[a[i]]++; deg[b[i]]++;
}
int most = 0;
for(int i = 1; i<= n; i++) most = max(most, deg[i]);
if(most == 2 && m == n-1)
{
st2(); return 0;
}
scanf("%d", &q);
for(int i = 1; i<= q; i++)
{
scanf("%d %d %d", &qq[i].t, &qq[i].a, &qq[i].b);
qq[i].id = i;
}
vector<int> edges;
for(int i = 1; i<= m; i++) edges.pb(i);
for(int i = 1; 1+(i-1)*lim<= q; i++)
{
int s = 1+(i-1)*lim;
int t = min(lim*i, q);
memset(chang, 0, sizeof chang);
vector<int> bad;
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1)
{
chang[qq[j].a] = true;
bad.pb(qq[j].a);
}
}
sort(bad.begin(), bad.end());
bad.resize(unique(bad.begin(), bad.end())-bad.begin());
sort(qq+s, qq+t+1);
int ptr = 0;
foo = dsu(n);
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1) continue;
while(ptr< m && w[edges[ptr]]>= qq[j].b)
{
if(chang[edges[ptr]])
{
ptr++;
continue;
}
foo.unite(a[edges[ptr]], b[edges[ptr]]);
// printf("unite %d %d\n", a[edges[ptr]], b[edges[ptr]]);
ptr++;
}
// printf("answering query %d\n", qq[j].id);
vector< ii > mod(bad.size(), {0, 0});
for(int k = s; k<= t; k++)
{
if(qq[k].t == 2) continue;
int x = lower_bound(bad.begin(), bad.end(), qq[k].a)-bad.begin();
mod[x] = max(mod[x], {0, w[qq[k].a]});
if(qq[k].id> qq[j].id) continue;
mod[x] = max(mod[x], {qq[k].id, qq[k].b});
}
int connt = 0;
int run = 0;
for(int u : bad)
{
if(mod[run++].Y>= qq[j].b)
{
connt += foo.unite(a[u], b[u]);
}
}
ans[qq[j].id] = foo.cc[foo.findset(qq[j].a)];
while(connt--) foo.rollback();
}
sort(qq+s, qq+t+1, cmp2);
for(int j = s; j<= t; j++)
{
if(qq[j].t == 1)
{
w[qq[j].a] = qq[j].b;
}
}
vector<int> still, dyn;
for(int e : edges)
{
if(chang[e])
{
dyn.pb(e);
}
else
{
still.pb(e);
}
}
sort(dyn.begin(), dyn.end(), cmp);
merge(edges, still, dyn);
}
for(int i = 1; i<= q; i++)
{
if(ans[i]) printf("%d\n", ans[i]);
}
}
컴파일 시 표준 에러 (stderr) 메시지
bridges.cpp: In function 'void st2()':
bridges.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:142:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t; scanf("%d", &t);
~~~~~^~~~~~~~~~
bridges.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &id, &c);
~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:151:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s, w; scanf("%d %d", &s, &w);
~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:205:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:208:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a[i], &b[i], &w[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:218:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:221:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &qq[i].t, &qq[i].a, &qq[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |