제출 #500081

#제출 시각아이디문제언어결과실행 시간메모리
500081kaxzert철인 이종 경기 (APIO18_duathlon)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; vi ADJ[2*MX]; int n,m,totsz[2*MX]; void ad(int a, int b) { ADJ[a].pb(b), ADJ[b].pb(a); } template<int SZ> struct BCC { int N, ti = 0; vi adj[SZ]; int disc[SZ], low[SZ], comp[SZ], par[SZ]; vector<vpi> fin; int compsz[SZ]; vpi st; void addEdge(int u, int v) { adj[u].pb(v), adj[v].pb(u); } void BCCutil(int u, bool root = 0) { disc[u] = low[u] = ti++; int child = 0; for (int i: adj[u]) if (i != par[u]) { if (disc[i] == -1) { child ++; par[i] = u; st.pb({u,i}); BCCutil(i); low[u] = min(low[u],low[i]); if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point! vpi tmp; while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back(); tmp.pb(st.back()), st.pop_back(); fin.pb(tmp); } } else if (disc[i] < disc[u]) { low[u] = min(low[u],disc[i]); st.pb({u,i}); } } } void bcc() { FOR(i,1,N+1) par[i] = disc[i] = low[i] = -1; FOR(i,1,N+1) if (disc[i] == -1) { BCCutil(i,1); if (sz(st)) fin.pb(st); st.clear(); } int co = 0; for (auto a: fin) { set<int> s; for (auto b: a) s.insert(b.f), s.insert(b.s); co ++; compsz[co] = sz(s); for (int i: s) ad(i,n+co); } } }; ll ans = 0; BCC<MX> B; bool visit[2*MX]; void dfs1(int x, int y = 0) { visit[x] = 1; if (x <= n) totsz[x] = 1; for (int i: ADJ[x]) if (i != y) { dfs1(i,x); totsz[x] += totsz[i]; } } void dfs2(int x, int p, int y = 0) { if (x <= n) { for (int i: ADJ[x]) { assert(i > n); if (i != y) { ans -= (ll)(B.compsz[i-n]-1)*(totsz[p]-totsz[i])*(totsz[p]-totsz[i]-1); } else { ans -= (ll)(B.compsz[i-n]-1)*totsz[x]*(totsz[x]-1); } } } for (int i: ADJ[x]) if (i != y) dfs2(i,p,x); } void init() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; F0R(i,m) { int a,b; cin >> a >> b; B.addEdge(a,b); } B.N = n; B.bcc(); } void genTree() { FOR(i,1,n+1) if (!visit[i]) { dfs1(i); ans += (ll)totsz[i]*(totsz[i]-1)*(totsz[i]-2); // cout << i << " " << totsz[i] << "\n"; dfs2(i,i); } } int main() { init(); genTree(); cout << ans; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */

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

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:104:5: error: reference to 'visit' is ambiguous
  104 |     visit[x] = 1; if (x <= n) totsz[x] = 1;
      |     ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from count_triplets.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
count_triplets.cpp:101:6: note:                 'bool visit [200002]'
  101 | bool visit[2*MX];
      |      ^~~~~
count_triplets.cpp: In function 'void genTree()':
count_triplets.cpp:137:23: error: reference to 'visit' is ambiguous
  137 |     FOR(i,1,n+1) if (!visit[i]) {
      |                       ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from count_triplets.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
count_triplets.cpp:101:6: note:                 'bool visit [200002]'
  101 | bool visit[2*MX];
      |      ^~~~~