제출 #1271773

#제출 시각아이디문제언어결과실행 시간메모리
1271773thuhienneBridges (APIO19_bridges)C++20
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define union __union__ const int can = 350; int n,m,q; struct __ { int u,v,w,index; bool operator < (const __ & other) { return w < other.w; } } edge[100009]; bool changed[100009]; int uniq,firsttime[100009]; int root[100009],size[100009]; int getroot(int node) { return (node == root[node] ? node : root[node] = getroot(root[node])); } void union(int u,int v) { u = getroot(u),v = getroot(v); if (u != v) root[u] = v,size[v] += size[u]; } struct data { int index,rootbefore,sizebefore,rootafter,sizeafter; }; int getroot(int node,vector <data> & record) { if (node == root[node]) return node; int d = getroot(root[node],record); record.push_back({node,root[node],size[node],d,size[node]}); root[node] = d; return d; } void union(int u,int v,vector <data> & record) { u = getroot(u,record); v = getroot(v,record); if (u == v) return; record.push_back({u,root[u],size[u],v,size[u]}); root[u] = v; record.push_back({v,root[v],size[v],root[v],size[v] + size[u]}); size[v] += size[u]; } void rollback(vector <data> & record) { reverse(record.begin(),record.end()); for (auto d : record) { root[d.index] = d.rootbefore; size[d.index] = d.sizebefore; } } struct query { int op,x,y,index; } ask[100009]; __ bridges[100009]; int answer[100009]; int main() { ios_base::sync_with_stdio(0);cin.tie(nullptr); //freopen(".inp","r",stdin); //freopen(".out","w",stdout); cin >> n >> m; for (int i = 1;i <= m;i++) { cin >> edge[i].u >> edge[i].v >> edge[i].w; edge[i].index = i; } cin >> q; for (int ____ = 0;;____++) { int l = max(1,____ * can),r = min(q,(____ + 1)*can - 1); vector <query> contain; for (int i = l;i <= r;i++) { cin >> ask[i].op >> ask[i].x >> ask[i].y; ask[i].index = i; if (ask[i].op == 1) { changed[ask[i].x] = 1; bridges[i] = edge[ask[i].x]; } else contain.push_back(ask[i]); } for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1; sort(contain.begin(),contain.end(),[] (query a,query b) { return a.y > b.y; }); sort(edge + 1,edge + 1 + m); int pt = m + 1; for (auto d : contain) { int minimum = d.y,island = d.x; while (pt > 1 && edge[pt - 1].w >= minimum) { pt--; if (!changed[edge[pt].index]) union(edge[pt].u,edge[pt].v); } vector <data> record; cout << "BEFORE:\n"; for (int i = 1;i <= n;i++) cout << root[i] << " "; cout << '\n'; uniq++; for (int i = d.index - 1;i >= l;i--) if (ask[i].op == 1) { cout << "DITCUMAY " << ask[i].x << " " << ask[i].y << '\n'; __ bridge = bridges[i]; int w = ask[i].y; if (firsttime[bridge.index] == uniq) continue; firsttime[bridge.index] = uniq; if (w >= minimum) union(bridge.u,bridge.v,record); } for (int i = d.index + 1;i <= r;i++) if (ask[i].op == 1) { __ bridge = bridges[i]; if (firsttime[bridge.index] == uniq) continue; if (bridge.w >= minimum) union(bridge.u,bridge.v,record); } answer[d.index] = size[getroot(island,record)]; rollback(record); } sort(edge + 1,edge + 1 + m,[] (__ a,__ b) { return a.index < b.index; }); for (int i = l;i <= r;i++) if (ask[i].op == 1) { changed[ask[i].x] = 0; edge[ask[i].x].w = ask[i].y; } if (r == q) break; } for (int i = 1;i <= q;i++) if (ask[i].op == 2) cout << answer[i] << '\n'; } /* Nho doi vai em gay co gai ay ngoi duoi goc pho nen tho ... */

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

bridges.cpp: In function 'void __union__(int, int)':
bridges.cpp:29:33: error: reference to 'size' is ambiguous
   29 |         if (u != v) root[u] = v,size[v] += size[u];
      |                                 ^~~~
In file included from /usr/include/c++/13/string:53,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from bridges.cpp:1:
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:29:44: error: reference to 'size' is ambiguous
   29 |         if (u != v) root[u] = v,size[v] += size[u];
      |                                            ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:36:34: error: template argument 1 is invalid
   36 | int getroot(int node,vector <data> & record) {
      |                                  ^
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:34: error: template argument 1 is invalid
bridges.cpp:36:34: error: template argument 2 is invalid
bridges.cpp:36:22: error: invalid template-id
   36 | int getroot(int node,vector <data> & record) {
      |                      ^~~~~~
bridges.cpp:36:30: error: reference to 'data' is ambiguous
   36 | int getroot(int node,vector <data> & record) {
      |                              ^~~~
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  346 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  336 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  325 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  314 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
bridges.cpp:32:8: note:                 'struct data'
   32 | struct data {
      |        ^~~~
bridges.cpp:36:22: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
   36 | int getroot(int node,vector <data> & record) {
      |                      ^~~~~~
      |                            <>
bridges.cpp:36:22: note: or use 'auto' for an abbreviated function template
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bridges.cpp: In function 'int getroot(...)':
bridges.cpp:38:36: error: 'record' was not declared in this scope
   38 |         int d = getroot(root[node],record);
      |                                    ^~~~~~
bridges.cpp:39:43: error: reference to 'size' is ambiguous
   39 |         record.push_back({node,root[node],size[node],d,size[node]});
      |                                           ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:39:56: error: reference to 'size' is ambiguous
   39 |         record.push_back({node,root[node],size[node],d,size[node]});
      |                                                        ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:43:36: error: template argument 1 is invalid
   43 | void union(int u,int v,vector <data> & record) {
      |                                    ^
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:36: error: template argument 1 is invalid
bridges.cpp:43:36: error: template argument 2 is invalid
bridges.cpp:43:24: error: invalid template-id
   43 | void union(int u,int v,vector <data> & record) {
      |                        ^~~~~~
bridges.cpp:43:32: error: reference to 'data' is ambiguous
   43 | void union(int u,int v,vector <data> & record) {
      |                                ^~~~
/usr/include/c++/13/bits/range_access.h:346:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(initializer_list<_Tp>)'
  346 |     data(initializer_list<_Tp> __il) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:336:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
  336 |     data(_Tp (&__array)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:325:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
  325 |     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:314:5: note:                 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
  314 |     data(_Container& __cont) noexcept(noexcept(__cont.data()))
      |     ^~~~
bridges.cpp:32:8: note:                 'struct data'
   32 | struct data {
      |        ^~~~
bridges.cpp:43:24: error: missing template argument list after 'std::vector'; template placeholder not permitted in parameter
   43 | void union(int u,int v,vector <data> & record) {
      |                        ^~~~~~
      |                              <>
bridges.cpp:43:24: note: or use 'auto' for an abbreviated function template
/usr/include/c++/13/bits/stl_vector.h:428:11: note: 'template<class _Tp, class _Alloc> class std::vector' declared here
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bridges.cpp: In function 'void __union__(...)':
bridges.cpp:44:23: error: 'record' was not declared in this scope
   44 |         u = getroot(u,record);
      |                       ^~~~~~
bridges.cpp:48:37: error: reference to 'size' is ambiguous
   48 |         record.push_back({u,root[u],size[u],v,size[u]});
      |                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:48:47: error: reference to 'size' is ambiguous
   48 |         record.push_back({u,root[u],size[u],v,size[u]});
      |                                               ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:37: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:53: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                                     ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:51:63: error: reference to 'size' is ambiguous
   51 |         record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
      |                                                               ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:52:9: error: reference to 'size' is ambiguous
   52 |         size[v] += size[u];
      |         ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:52:20: error: reference to 'size' is ambiguous
   52 |         size[v] += size[u];
      |                    ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp: At global scope:
bridges.cpp:56:27: error: template argument 1 is invalid
   56 | void rollback(vector <data> & record) {
      |                           ^
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:27: error: template argument 1 is invalid
bridges.cpp:56:27: error: template argument 2 is invalid
bridges.cpp:56:15: error: invalid template-id
   56 | void rollback(vector <data> & record) {
      |               ^~~~~~
bridges.cpp:56:6: error: variable or field 'rollback' declared void
   56 | void rollback(vector <data> & record) {
      |      ^~~~~~~~
bridges.cpp:56:29: error: missing template arguments before '&' token
   56 | void rollback(vector <data> & record) {
      |                             ^
bridges.cpp:56:31: error: 'record' was not declared in this scope
   56 | void rollback(vector <data> & record) {
      |                               ^~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:98:56: error: reference to 'size' is ambiguous
   98 |                 for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1;
      |                                                        ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:112:37: error: template argument 1 is invalid
  112 |                         vector <data> record;
      |                                     ^
bridges.cpp:112:37: error: template argument 2 is invalid
bridges.cpp:136:43: error: reference to 'size' is ambiguous
  136 |                         answer[d.index] = size[getroot(island,record)];
      |                                           ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  274 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  264 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
bridges.cpp:21:18: note:                 'int size [100009]'
   21 | int root[100009],size[100009];
      |                  ^~~~
bridges.cpp:138:25: error: 'rollback' was not declared in this scope
  138 |                         rollback(record);
      |                         ^~~~~~~~