제출 #1124373

#제출 시각아이디문제언어결과실행 시간메모리
1124373TVSownGrapevine (NOI22_grapevine)C++20
6 / 100
3110 ms364304 KiB
///*** Sown_Vipro ***/// /// ->TUYEN QUOC GIA<- /// #include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define all(a) a.begin(), a.end() #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); #define szz(s) int(s.size()) //#define int long long const int N = 1e5 + 5, MAX = 1e6, MOD = 1e9 + 7; const long long oo = 1e18; int n, q, TIME, tidel; int cnt[N], sz[N], del[N], in[N], out[N], nxt[N]; vector<pi> e[N]; vector<int> c[N]; vector<long long> m[N], lz[N], s[N]; map<int, pi> ti[N]; map<int, int> h[N]; map<pi, int> W; void down(int cen, int id){ if(lz[cen][id]){ s[cen][2 * id] += lz[cen][id]; if(m[cen][2 * id] < oo) m[cen][2 * id] += lz[cen][id]; lz[cen][2 * id] += lz[cen][id]; s[cen][2 * id + 1] += lz[cen][id]; if(m[cen][2 * id + 1] < oo) m[cen][2 * id + 1] += lz[cen][id]; lz[cen][2 * id + 1] += lz[cen][id]; lz[cen][id] = 0; } } void update(int cen, int id, int l, int r, int u, int v, long long x){ if(l > v || r < u) return; if(u <= l && r <= v){ s[cen][id] += x; if(m[cen][id] < oo) m[cen][id] += x; lz[cen][id] += x; return; } down(cen, id); int mid = (l + r) / 2; update(cen, 2 * id, l, mid, u, v, x); update(cen, 2 * id + 1, mid + 1, r, u, v, x); m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]); } void update2(int cen, int id, int l, int r, int i){ if(i > r || i < l) return; if(l == r){ c[cen][id] ^= 1; m[cen][id] = (c[cen][id] ? s[cen][id] : oo); // cout << s[cen][id] << "\n"; return; } down(cen, id); int mid = (l + r) / 2; update2(cen, 2 * id, l, mid, i); update2(cen, 2 * id + 1, mid + 1, r, i); m[cen][id] = min(m[cen][2 * id], m[cen][2 * id + 1]); } long long dis(int cen, int id, int l, int r, int u, int v){ if(l > v || r < u) return 0; if(u <= l && r <= v){ return s[cen][id]; } down(cen, id); int mid = (l + r) / 2; return dis(cen, 2 * id, l, mid, u, v) + dis(cen, 2 * id + 1, mid + 1, r, u, v); } void count_child(int u, int p){ cnt[u] = 1; for(auto [v, w] : e[u]){ if(v != p && !del[v]){ count_child(v, u); cnt[u] += cnt[v]; } } } int find_centroid(int u, int p, int n){ for(auto [v, w] : e[u]){ if(v != p && !del[v] && cnt[v] > (n / 2)) return find_centroid(v, u, n); } return u; } void dfs(int u, int p, long long W, int cen){ in[u] = ++TIME; // cout << u << " " << W << "\n"; update(cen, 1, 1, sz[cen], TIME, TIME, W); for(auto [v, w] : e[u]){ if(v != p && !del[v]){ h[cen][v] = h[cen][u] + 1; dfs(v, u, W + w, cen); } } out[u] = TIME; ti[cen][u] = {in[u], out[u]}; } void build(int u, int p){ count_child(u, p); int cen = find_centroid(u, p, cnt[u]); nxt[cen] = p; sz[cen] = cnt[u]; // cout << cen << " " << cnt[u] << "\n"; s[cen] = vector<long long> (4 * cnt[u], 0); c[cen] = vector<int> (4 * cnt[u], 0); m[cen] = vector<long long> (4 * cnt[u], oo); lz[cen] = vector<long long> (4 * cnt[u], 0); TIME = 0; dfs(cen, p, 0, cen); // cout << ti[cen][3].F << " " << dis(cen, 1, 1, sz[cen], ti[cen][3].F, ti[cen][3].F) << "\n"; del[cen] = ++tidel; for(auto [v, w] : e[cen]){ if(!del[v]) build(v, cen); } } void solve(){ cin >> n >> q; FOR(i, 2, n){ int u, v, w; cin >> u >> v >> w; e[u].pb({v, w}); e[v].pb({u, w}); W[{u, v}] = W[{v, u}] = w; } build(1, 0); while(q--){ int t; cin >> t; if(t == 1){ int s; cin >> s; long long res = oo, u = s; while(u != 0){ long long cost = dis(u, 1, 1, sz[u], ti[u][s].F, ti[u][s].F) + m[u][1]; // cout << u << " " << s << " " << cost << "\n"; res = min(res, cost); u = nxt[u]; } cout << (res > 1e14 ? -1 : res) << "\n"; }else if(t == 2){ int s; cin >> s; int u = s; while(u != 0){ update2(u, 1, 1, sz[u], ti[u][s].F); // cout << u << " " << s << " " << m[u][1] << "\n"; u = nxt[u]; } }else{ int s, t, w; cin >> s >> t >> w; if(del[s] > del[t]) swap(s, t); int u = s; while(u != 0){ if(h[u][s] > h[u][t]) swap(s, t); update(u, 1, 1, sz[u], ti[u][t].F, ti[u][t].S, w - W[{s, t}]); // cout << u << " " << s << " " << t << " " << w << " " << w - W[{s, t}] << " " << m[u][1] << "\n"; u = nxt[u]; } W[{s, t}] = W[{t, s}] = w; } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); inp("in.txt"); // out("out.txt"); int t = 1; // cin >> t; while(t--){ solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:17:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:191:5: note: in expansion of macro 'inp'
  191 |     inp("in.txt");
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...