제출 #501486

#제출 시각아이디문제언어결과실행 시간메모리
501486kaxzert철인 이종 경기 (APIO18_duathlon)C++17
0 / 100
104 ms39436 KiB
/** ⚡⚡ ⚡⚡ ⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡⚡⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡ ⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡⚡⚡⚡⚡ ⚡⚡⚡⚡⚡ ⚡⚡ ⚡⚡ ⚡⚡ **/ #include<bits/stdc++.h> using namespace std; #define fto(i, a, b) for(int i = a; i <= b; ++i) #define fdto(i, a, b) for(int i = a; i >= b; --i) #define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl; #define ll long long #define db double #define ldb long double #define ff first #define ss second #define pb push_back #define mp make_pair #define eb emplace_back #define vt vector #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define trav(i, a) for(auto &i : a) #define sz(a) (int)a.size() #define pi(a, b) pair<a, b> #define fast ios::sync_with_stdio(false); cin.tie(0) string to_bit(int n) { string res = ""; while(n > 0) { res += to_string(n&1); n >>= 1; } return res; } void setIO(string s) { if (sz(s) != 0) { freopen((s+".inp").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } void setIOusaco(string s) { if (sz(s) != 0) { freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } template<typename T, typename V> bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;} template<typename T, typename V> bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;} void print(int x) {cout << x;} void print(long long x) {cout << x;} void print(unsigned x) {cout << x;} void print(unsigned long long x) {cout << x;} void print(double x) {cout << fixed << x;} void print(long double x) {cout << fixed << x;} void print(char x) {cout << "'" << x << "'";} void print(string x) {cout << '"' << x << '"';} void print(bool x) {cout << (x ? "true" : "false");} template<typename T, typename V> void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';} template<typename T> void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";} void _print() {cout << "]" << endl;} template <typename T, typename... V> void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);} #ifdef TAP #define bug(x...) cout << "[" << #x << "] = ["; _print(x) #else #define bug(x...) #endif const int maxN = 100008; int low[maxN], num[maxN*4], cnt, color[maxN], articulation[maxN], root, child, dd[maxN]; vt<int> ke[maxN], block_ke[maxN*4]; ll cnt_color[maxN*4], ans, n, m; vt<vt<pi(int, int)> > bvccs; stack<pi(int, int)> s; void dfs(int u, int p = 0) { num[u] = low[u] = ++cnt; trav(v, ke[u]) { if (v == p) continue; if (num[v] == 0) { s.push({u, v}); if (u == root) ++child; dfs(v, u); if (low[v] >= num[u]) { articulation[u] = 1; vt<pi(int, int)> bvcc; while(s.top().ff != u || s.top().ss != v) { bvcc.pb(s.top()); s.pop(); } bvcc.pb(s.top()); s.pop(); bvccs.pb(bvcc); } ckmin(low[u], low[v]); } else { if (num[u] > num[v]) s.push({u, v}); ckmin(low[u], num[v]); } } } ll dfs2(int u, int p = 0, int is_cut = 1) { num[u] = 1; ll res = (is_cut ? 1 : cnt_color[u]); trav(v, block_ke[u]) { if (v == p) continue; ll sth = dfs2(v, u, is_cut^1); // bug(u, p, is_cut); // bug(sth); res += sth; if (is_cut == 1) ans += (is_cut ? 1LL : cnt_color[u])*(cnt_color[v]*(cnt_color[v]-1)); ans -= (is_cut ? 1 : cnt_color[u])*(sth*(sth-1)); // bug(ans); } if (is_cut == 1 && p != 0) if (is_cut&1) ans += (is_cut ? 1LL : cnt_color[u])*(cnt_color[p]*(cnt_color[p]-1)); ans -= (is_cut ? 1 : cnt_color[u])*((n-res)*(n-res-1)); // bug(u, p, is_cut); //bug(n-res); //bug(ans); return res; } int main() { #ifndef TAP setIO(""); //setIOusaco("duatholon2018"); #endif fast; cin >> n >> m; fto(i, 1, m) { int u, v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); } fto(i, 1, n) { if (num[i] == 0) { root = i; child = 0; dfs(i, 0); articulation[i] = (child > 1); } } int dem = 0; fto(i, 1, n) { if (articulation[i]) { color[i] = ++dem; } } auto add = [&](int u) -> void { if (articulation[u]) { if (dd[u] != dem) { block_ke[dem].pb(color[u]); block_ke[color[u]].pb(dem); dd[u] = dem; } } else { cnt_color[dem] += dd[u]^1; dd[u] |= 1; color[u] = dem; } }; vt<int> dd(n+1, 0); trav(bvcc, bvccs) { ++dem; trav(canh, bvcc) { add(canh.ff); add(canh.ss); } } // fto(i, 1, n) { // cout << color[i] << ' '; // } // cout << '\n'; fto(i, 1, dem) { num[i] = 0; } ans = n*(n-1)*(n-2); fto(i, 1, dem) { if (num[i] == 0) { dfs2(i); } } cout << ans << '\n'; return 0; }

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

count_triplets.cpp: In function 'void setIO(std::string)':
count_triplets.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void setIOusaco(std::string)':
count_triplets.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...