이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;
typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;
const int maxN = int(1e5)+7;
const int LOG = 17;
int n , q;
map<ii , int> c;
vector<int> g[maxN];
bool del[maxN];
int sz[maxN];
void dfs_size(int u , int par){
sz[u] = 1;
for (int v : g[u]){
if (del[v] == 0 && v != par){
dfs_size(v , u);
sz[u] += sz[v];
}
}
}
int dfs_find(int u , int par , int half){
for (int v : g[u]){
if (del[v] == 0 && v != par && sz[v] > half){
return dfs_find(v , u , half);
}
}
return u;
}
int p[maxN] , h[maxN] , in[LOG + 1][maxN] , out[LOG + 1][maxN] , DfsTime = 0;
void dfs_build(int u , int par , int d){
in[d][u] = ++DfsTime;
for (int v : g[u]){
if (del[v] == 0 && v != par){
dfs_build(v , u , d);
}
}
out[d][u] = DfsTime;
}
void dfs_centroid(int u , int par){
dfs_size(u , 0);
u = dfs_find(u , 0 , sz[u] / 2);
del[u] = 1;
p[u] = par;
h[u] = (par != 0) ? h[par] + 1 : 0;
dfs_build(u , 0 , h[u]);
for (int v : g[u]){
if (del[v] == 0){
dfs_centroid(v , u);
}
}
}
const ll inf = ll(1e17);
struct node{
ll val , lazy;
};
node st[4 * LOG * maxN];
void init(){
for (int id = 1 ; id <= 4 * DfsTime ; id++){
st[id].val = inf;
st[id].lazy = 0;
}
}
void modify(int id , ll x){
st[id].val += x;
st[id].lazy += x;
}
#define lef(id) id * 2
#define rig(id) id * 2 + 1
void down(int id){
ll &x = st[id].lazy;
if (x == 0) return;
modify(lef(id) , x);
modify(rig(id) , x);
x = 0;
}
void update(int id , int l , int r , int u , int v , ll x){
if (v < l || r < u) return;
if (u <= l && r <= v) return modify(id , x);
if (l != r) down(id);
int mid = (l + r) / 2;
update(lef(id) , l , mid , u , v , x);
update(rig(id) , mid + 1 , r , u , v , x);
st[id].val = min(st[lef(id)].val , st[rig(id)].val);
}
ll get(int id , int l , int r , int u , int v){
if (v < l || r < u) return 2 * inf;
if (u <= l && r <= v) return st[id].val;
if (l != r) down(id);
int mid = (l + r) / 2;
return min(get(lef(id) , l , mid , u , v) , get(rig(id) , mid + 1 , r , u , v));
}
void update(int u , int v , ll w){
int x = (h[u] < h[v]) ? u : v;
for (; x != 0 ; x = p[x]){
if (in[h[x]][u] > in[h[x]][v]) swap(u , v);
update(1 , 1 , DfsTime , in[h[x]][v] , out[h[x]][v] , +w);
}
}
bool type[maxN];
void update(int u){
if (type[u] == 0){
type[u] = 1;
for (int x = u ; x != 0 ; x = p[x]){
update(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u] , -inf);
}
}
else{
type[u] = 0;
for (int x = u ; x != 0 ; x = p[x]){
update(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u] , +inf);
}
}
}
ll get(int u){
ll ans = inf;
for (int x = u ; x != 0 ; x = p[x]){
ll a = get(1 , 1 , DfsTime , in[h[x]][u] , in[h[x]][u]);
if (type[u] == 0) a -= inf;
ll b = get(1 , 1 , DfsTime , in[h[x]][x] , out[h[x]][x]);
ans = min(ans , a + b);
}
if (ans == inf) ans = -1;
return ans;
}
void solve(){
cin >> n >> q;
for (int i = 1 ; i < n ; i++){
int u , v , w;
cin >> u >> v >> w;
g[u].push_back(v);
g[v].push_back(u);
c[{min(u , v) , max(u , v)}] = w;
}
dfs_centroid(1 , 0);
init();
for (auto it : c){
int u = it.fi.fi;
int v = it.fi.se;
int w = it.se;
update(u , v , w);
}
while (q--){
int t; cin >> t;
if (t == 1){
int u; cin >> u;
cout << get(u) << "\n";
}
if (t == 2){
int u; cin >> u;
update(u);
}
if (t == 3){
int u , v , w;
cin >> u >> v >> w;
ii it = {min(u , v) , max(u , v)};
update(u , v , w - c[it]);
c[it] = w;
}
}
}
#define name "A"
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(name".INP" , "r")){
freopen(name".INP" , "r" , stdin);
freopen(name".OUT" , "w" , stdout);
}
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen(name".INP" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
196 | freopen(name".OUT" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |