제출 #1042084

#제출 시각아이디문제언어결과실행 시간메모리
1042084RecursiveCo자매 도시 (APIO20_swap)C++17
6 / 100
158 ms33044 KiB
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} //#define int long long int template <typename T, typename I> struct segtree { int n; vector<T> tree; vector<I> initial; T id; segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) { tree.resize(4 * n); } T conquer(T left, T right) { // write your conquer function } T value(I inp) { // write your value function } void build(int v, int l, int r) { if (l == r) tree[v] = value(initial[l]); else { int middle = (l + r) / 2; build(2 * v, l, middle); build(2 * v + 1, middle + 1, r); tree[v] = conquer(tree[2 * v], tree[2 * v + 1]); } } void upd(int v, int l, int r, int i, I x) { if (l == r) tree[v] = value(x); else { int middle = (l + r) / 2; if (middle >= i) upd(2 * v, l, middle, i, x); else upd(2 * v + 1, middle + 1, r, i, x); tree[v] = conquer(tree[2 * v], tree[2 * v + 1]); } } T query(int v, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tree[v]; else if (r < ql || qr < l) return id; int middle = (l + r) / 2; T left = query(2 * v, l, middle, ql, qr); T right = query(2 * v + 1, middle + 1, r, ql, qr); return conquer(left, right); } }; // vector<int> vector<int> parent; vector<vector<int>> comps; vector<int> deg; vector<int> maxdeg; vector<int> edges; vector<bool> marked; vector<int> nonline; vector<vector<pair<int, int>>> merges; int find(int v) { if (v == parent[v]) return v; return parent[v] = find(parent[v]); } void unite(int u, int v, int val) { int a = find(u); int b = find(v); deg[u]++; deg[v]++; if (a == b) { maxdeg[a] = max({maxdeg[a], deg[u], deg[v]}); edges[a]++; if (!marked[a] && (maxdeg[a] >= 3 || edges[a] == comps[a].size())) { marked[a] = true; for (int node: comps[a]) nonline[node] = min(nonline[node], val); } } else { if (comps[a].size() > comps[b].size()) swap(a, b); if (marked[a] && !marked[b]) for (int node: comps[b]) nonline[node] = min(nonline[node], val); while (!comps[a].empty()) { int node = comps[a].back(); comps[a].pop_back(); comps[b].push_back(node); merges[node].push_back({val, b}); maxdeg[b] = max(maxdeg[b], deg[node]); if (marked[b] && !marked[a]) nonline[node] = min(nonline[node], val); } if (!marked[a] && !marked[b] && (maxdeg[b] >= 3 || edges[b] == comps[b].size())) { marked[b] = true; for (int node: comps[b]) nonline[node] = min(nonline[node], val); } parent[a] = b; edges[b] += edges[a] + 1; } } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { forto(N, i) { parent.push_back(i); vector<int> here1; here1.push_back(i); comps.push_back(here1); deg.push_back(0); maxdeg.push_back(0); edges.push_back(0); marked.push_back(false); nonline.push_back(1e9 + 5); vector<pair<int, int>> here2; merges.push_back(here2); } vector<array<int, 3>> sorted; forto(M, i) sorted.push_back({W[i], U[i], V[i]}); sortl(sorted); forto(M, i) { int w = sorted[i][0]; int u = sorted[i][1]; int v = sorted[i][2]; unite(u, v, w); } } int getMinimumFuelCapacity(int X, int Y) { int one = nonline[X]; if (one == 1e9 + 5) return -1; vector<array<int, 3>> events; for (pair<int, int> event: merges[X]) events.push_back({event.first, event.second, 0}); for (pair<int, int> event: merges[Y]) events.push_back({event.first, event.second, 1}); sortl(events); int parX = X; int parY = Y; int two; for (array<int, 3> event: events) { if (event[2] == 0) parX = event[1]; else parY = event[1]; if (parX == parY) { two = event[0]; break; } } return max(one, two); }

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

swap.cpp: In function 'void unite(int, int, int)':
swap.cpp:93:55: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         if (!marked[a] && (maxdeg[a] >= 3 || edges[a] == comps[a].size())) {
swap.cpp:108:69: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (!marked[a] && !marked[b] && (maxdeg[b] >= 3 || edges[b] == comps[b].size())) {
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
swap.cpp:118:5: note: in expansion of macro 'forto'
  118 |     forto(N, i) {
      |     ^~~~~
swap.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
swap.cpp:140:5: note: in expansion of macro 'forto'
  140 |     forto(M, i) sorted.push_back({W[i], U[i], V[i]});
      |     ^~~~~
swap.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
swap.cpp:142:5: note: in expansion of macro 'forto'
  142 |     forto(M, i) {
      |     ^~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:159:9: warning: 'two' may be used uninitialized in this function [-Wmaybe-uninitialized]
  159 |     int two;
      |         ^~~
#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...