제출 #243713

#제출 시각아이디문제언어결과실행 시간메모리
243713SamAndRoadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
90 ms16632 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 100005; int n; vector<int> g[N], gd[N]; const int m = 18; int p[N][m]; int d[N]; int tin[N], tout[N], ti; void dfs(int x, int p0) { tin[x] = ++ti; p[x][0] = p0; for (int i = 1; i < m; ++i) p[x][i] = p[p[x][i - 1]][i - 1]; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p0) continue; d[h] = d[x] + gd[x][i]; dfs(h, x); } tout[x] = ti; } bool isp(int x, int y) { return (tin[x] <= tin[y] && tout[y] <= tout[x]); } int lca(int x, int y) { if (isp(x, y)) return x; if (isp(y, x)) return y; for (int i = m - 1; i >= 0; --i) { if (!isp(p[x][i], y)) x = p[x][i]; } return p[x][0]; } bool so(int x, int y) { return tin[x] < tin[y]; } int dist(int x, int y) { return d[x] + d[y] - 2 * d[lca(x, y)]; } void solv() { scanf("%d", &n); for (int i = 0; i < n - 1; ++i) { int x, y, d; scanf("%d%d%d", &x, &y, &d); g[x].push_back(y); g[y].push_back(x); gd[x].push_back(d); gd[y].push_back(d); } dfs(0, 0); int qq; scanf("%d", &qq); while (qq--) { int x[5]; for (int i = 0; i < 5; ++i) { scanf("%d", &x[i]); } sort(x, x + 5, so); int ans = 0; ans += dist(lca(x[0], x[4]), x[0]); for (int i = 0; i < 5 - 1; ++i) ans += dist(x[i], x[i + 1]); ans += dist(lca(x[0], x[4]), x[4]); printf("%d\n", ans / 2); } } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING //ios_base::sync_with_stdio(false), cin.tie(0); solv(); return 0; } //while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

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

roadsideadverts.cpp: In function 'void dfs(int, int)':
roadsideadverts.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void solv()':
roadsideadverts.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
roadsideadverts.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qq);
     ~~~~~^~~~~~~~~~~
roadsideadverts.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x[i]);
             ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...