제출 #710726

#제출 시각아이디문제언어결과실행 시간메모리
710726Clan328전선 연결 (IOI17_wiring)C++17
0 / 100
191 ms66976 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; vvi G, W; vi p, visited; vector<vector<ll>> dp; void dfs(int v, int par) { visited[v] = true; p[v] = par; for (auto u : G[v]) { if (u == par) continue; if (visited[u]) continue; dfs(u, v); } } ll getDP(int v, bool needsGroup) { if (dp[v][needsGroup] != -1) return dp[v][needsGroup]; if (p[v] != -1) { if (G[v].size() == 1 && needsGroup) { dp[v][needsGroup] = INT_MAX; return dp[v][needsGroup]; } else if (G[v].size() == 1 && !needsGroup) { dp[v][needsGroup] = 0; return dp[v][needsGroup]; } } ll res = 0; ll minX = INT_MAX; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i]; if (u == p[v]) continue; if (!needsGroup) { res += min(getDP(u, 0)+W[v][i], getDP(u, 1)); } else { if (getDP(u, 1) == INT_MAX) { res += getDP(u, 0)+W[v][i]; minX = 0; } else { res += getDP(u, 1); minX = min(minX, getDP(u, 0)+W[v][i] - getDP(u, 1)); } } } if (needsGroup) { res += minX; } dp[v][needsGroup] = res; return res; } ll min_total_length(vi r, vi b) { int n = r.size(), m = b.size(); vi a; vi left(n+m), right(n+m); int lastR = -1, lastB = -1; int idxA = 0, idxB = 0; while (idxA < n || idxB < m) { if (idxA < n && (idxB >= m || r[idxA] < b[idxB])) { left[idxA+idxB] = lastB; lastR = idxA+idxB;//r[idxA]; a.pb(r[idxA]); idxA++; } else { left[idxA+idxB] = lastR; lastB = idxA+idxB;//b[idxB]; a.pb(b[idxB]); idxB++; } } lastR = -1, lastB = -1; idxA = n-1, idxB = m-1; while (idxA >= 0 || idxB >= 0) { if (idxA >= 0 && (idxB < 0 || r[idxA] > b[idxB])) { right[idxA+idxB+1] = lastB; lastR = idxA+idxB+1;//r[idxA]; idxA--; } else { right[idxA+idxB+1] = lastR; lastB = idxA+idxB+1;//b[idxB]; idxB--; } } G = vvi(n+m); W = vvi(n+m); map<pair<int, int>, int> doubleEdge; for (int i = 0; i < n+m; i++) { int d1 = left[i] != -1? a[i]-a[left[i]] : INT_MAX; int d2 = right[i] != -1? a[right[i]]-a[i] : INT_MAX; if ((d1 <= d2) && left[i] != -1 && doubleEdge.count({i, left[i]}) == 0) { G[i].pb(left[i]); W[i].pb(a[i]-a[left[i]]); G[left[i]].pb(i); W[left[i]].pb(a[i]-a[left[i]]); doubleEdge[{i, left[i]}] = doubleEdge[{left[i], i}] = 1; } // cout << d1 << " " << d2 << endl; if ((d2 <= d1) &&right[i] != -1 && doubleEdge.count({i, right[i]}) == 0) { G[i].pb(right[i]); W[i].pb(a[right[i]]-a[i]); G[right[i]].pb(i); W[right[i]].pb(a[right[i]]-a[i]); doubleEdge[{i, right[i]}] = doubleEdge[{right[i], i}] = 1; } } int k = 0; for (int i = 0; i < n+m; i++) { for (int j = 0; j < G[i].size(); j++) { if (i >= G[i][j]) continue; // cout << i << " " << G[i][j] << " " << W[i][j] << endl; k += W[i][j]; } } // return k; // for (int i = 0; i < n+m; i++) cout << right[i] << " "; // cout << endl; p = vi(n+m); visited = vi(n+m); for (int i = 0; i < n+m; i++) { if (visited[i]) continue; if (G[i].size() == 1) { dfs(i, -1); } } dp = vector<vector<ll>>(n+m, vector<ll>(2, -1)); int res = 0; for (int i = 0; i < n+m; i++) { if (dp[i][1] != -1) continue; if (G[i].size() == 1) { res += getDP(i, 1); // cout << getDP(i, 1) << endl; } } return res; }

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

wiring.cpp: In function 'll getDP(int, bool)':
wiring.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < G[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(vi, vi)':
wiring.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int j = 0; j < G[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~
#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...