| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749524 |
2023-05-28T07:02:19 Z |
반딧불(#9967) |
Grapevine (NOI22_grapevine) |
C++17 |
|
1366 ms |
163784 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segmentTree{
int SZ;
vector<ll> tree, lazy;
void init(int n){
SZ = n;
tree.resize(n*4+1), lazy.resize(n*4+1);
init(1, 1, n);
}
void init(int i, int l, int r){
tree[i] = 1e18;
lazy[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] += lazy[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void add(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
add(i*2, l, m, s, e, v);
add(i*2+1, m+1, r, s, e, v);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 1e18;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
ll query(){
return query(1, 1, SZ, 1, SZ);
}
} tree[100002];
struct Line{
int nxt, idx;
Line(){}
Line(int nxt, int idx): nxt(nxt), idx(idx){}
};
int n, q;
int ex[100002], ey[100002];
ll len[100002];
vector<Line> link[100002];
bool on[100002];
namespace HLD{
struct Fenwick{
int n;
ll tree[100002];
void init(int _n){
n = _n;
for(int i=1; i<=n; i++) tree[i] = 0;
}
void _add(int x, ll v){
while(x<=n){
tree[x] += v;
x += x&-x;
}
}
void add(int s, int e, ll v){
_add(s, v);
_add(e+1, -v);
}
ll _sum(int x){
ll ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
ll sum(int x){
return _sum(x);
}
} tree;
int par[100002];
int in[100002], out[100002], depth[100002], inCnt;
int LCADB[100002][20];
void dfs(int x, int p=-1){
in[x] = ++inCnt;
for(Line y: link[x]){
if(y.nxt == p) continue;
par[y.nxt] = x;
depth[y.nxt] = depth[x] + 1;
dfs(y.nxt, x);
}
out[x] = inCnt;
}
void init(){
dfs(1);
for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
tree.init(n);
for(int i=1; i<n; i++){
int x = ex[i], y = ey[i];
if(depth[x] < depth[y]) swap(x, y);
/// x�� �� �Ʒ��� �ִ� ����
tree.add(in[x], out[x], len[i]);
}
}
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
ll query(int a, int b){
int c = getLCA(a, b);
return tree.sum(in[a]) + tree.sum(in[b]) - tree.sum(in[c])*2;
}
void update(int x, ll v){
tree.add(in[x], out[x], v);
}
}
bool centroidUsed[100002];
int centroidRoot, centroidPar[100002], centroidDepth[100002];
int subtreeSize[100002];
int sz[100002], in[100002][20], out[100002][20], depth[100002][20];
int canFindEdges[100002][20];
void getSubtreeSize(int x, int p=-1){
subtreeSize[x] = 1;
for(auto y: link[x]){
if(y.nxt==p || centroidUsed[y.nxt]) continue;
getSubtreeSize(y.nxt, x);
subtreeSize[x] += subtreeSize[y.nxt];
}
}
int getCentroid(int x, int p, int lim){
for(auto y: link[x]){
if(y.nxt==p || centroidUsed[y.nxt]) continue;
if(subtreeSize[y.nxt] >= lim) return getCentroid(y.nxt, x, lim);
}
return x;
}
void eulerTourDfs(int x, int p, int d, int c){
in[x][d] = ++sz[c];
for(auto y: link[x]){
if(y.nxt == p || centroidUsed[y.nxt]) continue;
canFindEdges[y.nxt][d] = c;
depth[y.nxt][d] = depth[x][d] + 1;
eulerTourDfs(y.nxt, x, d, c);
}
out[x][d] = sz[c];
}
void putLengthDfs(int x, int p, int d, int c){
for(auto y: link[x]){
if(y.nxt == p || centroidUsed[y.nxt]) continue;
tree[c].add(1, 1, sz[c], in[y.nxt][d], out[y.nxt][d], len[y.idx]);
putLengthDfs(y.nxt, x, d, c);
}
}
int findCentroid(int x, int d = 0){
getSubtreeSize(x);
x = getCentroid(x, -1, (subtreeSize[x] + 1) / 2);
centroidUsed[x] = 1;
centroidDepth[x] = d;
depth[x][d] = 0;
eulerTourDfs(x, -1, d, x);
tree[x].init(sz[x]);
putLengthDfs(x, -1, d, x);
for(auto y: link[x]){
if(centroidUsed[y.nxt]) continue;
int tmp = findCentroid(y.nxt, d+1);
centroidPar[tmp] = x;
}
return x;
}
ll getAnswer(int x){
int c = x;
ll ret = 1e18;
while(c){
ret = min(ret, HLD::query(c, x) + tree[c].query());
c = centroidPar[c];
}
assert(ret <= 1e17);
return ret;
}
void changeVertex(int x){
int c = x;
ll v = (on[x] ? 1e18 : -1e18);
on[x] = !on[x];
while(c){ /// ��Ʈ���̵带 ���ƴٴϸ� +, - ���ֱ�
int d = centroidDepth[c];
tree[c].add(1, 1, sz[c], in[x][d], in[x][d], v);
c = centroidPar[c];
}
}
void changeEdge(int idx, ll v){
/// HLD ������ ����
assert(idx);
int x = ex[idx], y = ey[idx];
if(HLD::depth[x] < HLD::depth[y]) swap(x, y);
HLD::update(x, v - len[idx]);
for(int d=19; d>=0; d--){ /// ��Ʈ���̵� ������ ����
if(!canFindEdges[idx][d]) continue;
int x = ex[idx], y = ey[idx], c = canFindEdges[idx][d];
if(depth[x][d] < depth[y][d]) swap(x, y); /// ���� x�� �� �Ʒ���
tree[c].add(1, 1, sz[c], in[x][d], out[x][d], v - len[idx]);
}
len[idx] = v;
}
int main(){
map<pair<int, int>, int> mpEdge;
scanf("%d %d", &n, &q);
for(int i=1; i<n; i++){
int x, y; ll w;
scanf("%d %d %lld", &x, &y, &w);
ex[i] = x, ey[i] = y, len[i] = w;
link[x].push_back(Line(y, i));
link[y].push_back(Line(x, i));
mpEdge[make_pair(x, y)] = mpEdge[make_pair(y, x)] = i;
}
centroidRoot = findCentroid(1);
HLD::init();
int grapeCnt = 0;
while(q--){
int qt;
scanf("%d", &qt);
if(qt == 1){ /// Seek the nearest
int x;
scanf("%d", &x);
if(!grapeCnt) puts("-1");
else printf("%lld\n", getAnswer(x));
}
else if(qt == 2){ /// ���� ������Ʈ
int x;
scanf("%d", &x);
grapeCnt += (on[x] ? -1 : 1);
changeVertex(x);
}
else{
int a, b; ll w;
scanf("%d %d %lld", &a, &b, &w);
changeEdge(mpEdge[make_pair(a, b)], w);
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:258:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
258 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:261:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
261 | scanf("%d %d %lld", &x, &y, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:273:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
273 | scanf("%d", &qt);
| ~~~~~^~~~~~~~~~~
Main.cpp:276:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
276 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:282:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
282 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:288:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
288 | scanf("%d %d %lld", &a, &b, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
10452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1202 ms |
146156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1125 ms |
163784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1295 ms |
144548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1366 ms |
147884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
10452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
