제출 #380576

#제출 시각아이디문제언어결과실행 시간메모리
380576GioChkhaidzeTransport (COCI19_transport)C++14
78 / 130
380 ms30692 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define F first #define S second using namespace std; const int N = 1e5 + 5; ll ans; bool f[N]; vector < int > s[N]; int n, rec, P, C, a[N]; vector < pair < int , int > > v[N]; int get(int x, int u) { int l = 0, r = s[x].size() - 1, mid, res = 0; while (l <= r) { mid = (l + r) >> 1; if (u + s[x][mid] >= 0) res = s[x].size() - mid, r = mid - 1; else l = mid + 1; } return res; } int find_center(int x, int p, int &cen, int num) { int tot = 1; for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i].F; if (f[to] || to == p) continue; tot += find_center(to, x, cen, num); } if (cen == -1 && (2 * tot >= num || x == p)) cen = x; return tot; } void fromc(int x, int p, int recm, int rec) { if (recm >= 0) ++ans; s[P].push_back(recm); s[C].push_back(recm); for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i].F, cost = a[x] - v[x][i].S; if (f[to] || to == p) continue; fromc(to, x, min(recm, rec + cost), rec + cost); } } void ansc(int x, int p, int recm, int rec) { if (recm >= 0) { ans += get(C, rec) - get(P, rec); ++ans; } for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i].F, cost = a[to] - v[x][i].S; if (f[to] || to == p) continue; ansc(to, x, min(recm + cost, cost), rec + cost); } } void Centroid(int x, int num) { int cen = -1; find_center(x, x, cen, num); f[cen] = true; C = cen; for (int i = 0; i < v[cen].size(); ++i) { int to = v[cen][i].F, cost = a[cen] - v[cen][i].S; P = to; if (f[to]) continue; fromc(to, cen, cost, cost); sort(s[to].begin(), s[to].end()); } sort(s[cen].begin(), s[cen].end()); for (int i = 0; i < v[cen].size(); ++i) { int to = v[cen][i].F, cost = a[to] - v[cen][i].S; P = to; if (f[to]) continue; ansc(to, cen, cost, cost); } s[cen].clear(); for (int i = 0; i < v[cen].size(); ++i) { int to = v[cen][i].F; if (f[to]) continue; s[to].clear(); Centroid(to, num / 2); } } main () { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i < n; ++i) { int a, b, c; cin >> a >> b >> c; v[a].pb({b, c}); v[b].pb({a, c}); } Centroid(1, n); cout << ans << "\n"; }

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

transport.cpp: In function 'int find_center(int, int, int&, int)':
transport.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void fromc(int, int, int, int)':
transport.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void ansc(int, int, int, int)':
transport.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
transport.cpp: In function 'void Centroid(int, int)':
transport.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < v[cen].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~
transport.cpp: At global scope:
transport.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main () {
      |       ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...