제출 #556990

#제출 시각아이디문제언어결과실행 시간메모리
556990Tien_NoobValley (BOI19_valley)C++17
23 / 100
326 ms46628 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" #define Log2(x) 31 - __builtin_clz(x) using namespace std; const int N = 1e5; const long long oo = 1e18; long long dp[N + 1], f[N + 1]; int n, s, q, root, tin[N + 1], depth[N + 1], tout[N + 1], timer, l[N], r[N], w[N]; vector<int> adj[N + 1]; vector<pair<int, int> > query[N + 1]; bool shop[N + 1]; long long res[N + 1]; void read() { cin >> n >> s >> q >> root; for (int i = 1; i < n; ++ i) { cin >> l[i] >> r[i] >> w[i]; adj[l[i]].push_back(i); adj[r[i]].push_back(i); } for (int i = 1; i <= s; ++ i) { int u; cin >> u; shop[u] = true; } for (int i = 1; i <= q; ++ i) { int I, R; cin >> I >> R; query[R].push_back({I, i}); } depth[root] = 1; fill(res, res + q + 1, oo); } struct FenwickTree { multiset<long long> tree[N + 1]; void add(int pos, long long val) { for (; pos > 0; pos -= (pos & (-pos))) { tree[pos].insert(val); } } long long get(int pos) { long long ret = oo; for (; pos <= n; pos += (pos & (-pos))) { if (!tree[pos].empty()) { ret = min(ret, *tree[pos].begin()); } } return ret; } void del(int pos, long long val) { for (; pos > 0; pos -= (pos & (-pos))) { auto it = tree[pos].find(val); if (it != tree[pos].end()) { tree[pos].erase(it); } } } } tree; void preDFS(int u, int p) { tin[u] = ++timer; if (shop[u]) { dp[u] = f[u]; } else { dp[u] = oo; } for (int i : adj[u]) { int v = l[i] ^ r[i] ^ u; if (v == p) { continue; } f[v] = f[u] + w[i]; depth[v] = depth[u] + 1; preDFS(v, u); dp[u] = min(dp[u], dp[v]); } tout[u] = timer; } void DFS(int u, int p) { if (dp[u] != oo) { tree.add(depth[u], dp[u] - 2 * f[u]); } for (auto &x : query[u]) { if (depth[l[x.first]] > depth[r[x.first]]) { swap(l[x.first], r[x.first]); } int b = r[x.first]; if (tin[u] < tin[b] || tin[u] > tout[b]) { res[x.second] = -1; continue; } long long t = tree.get(depth[b]); if (t != oo) { res[x.second] = t + f[u]; } } for (int i : adj[u]) { int v = l[i] ^ r[i] ^ u; if (v == p) { continue; } DFS(v, u); } if (dp[u] != oo) { tree.del(depth[u], dp[u] - 2 * f[u]); } } void solve() { preDFS(root, 0); DFS(root, 0); for (int i = 1; i <= q; ++ i) { if (res[i] == -1) { cout << "escaped" << '\n'; } else if (res[i] == oo) { cout << "oo"; } else { cout << res[i] << '\n'; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

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

valley.cpp: In function 'int main()':
valley.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...