제출 #557827

#제출 시각아이디문제언어결과실행 시간메모리
557827nutella철인 이종 경기 (APIO18_duathlon)C++17
0 / 100
1108 ms1048576 KiB
//#define _GLIBCXX_DEBUG //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; //#include <ext/pb_ds/assoc_container.hpp> // //using namespace __gnu_pbds; // //template<typename T> //using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<>>; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); #define trace(x) cout << #x << ": " << (x) << endl; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define uniq(x) x.resize(unique(all(x)) - begin(x)) #define sz(s) ((int) size(s)) #define pii pair<int, int> #define mp(x, y) make_pair(x, y) #define int128 __int128 #define pb push_back #define popb pop_back #define eb emplace_back #define fi first #define se second #define itn int typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; typedef double db; typedef unsigned int uint; template<typename T> bool ckmn(T &x, T y) { if (x > y) { x = y; return true; } return false; } template<typename T> bool ckmx(T &x, T y) { if (x < y) { x = y; return true; } return false; } int bit(int x, int b) { return (x >> b) & 1; } int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; } const ll infL = 3e18; const int infI = 1000000000 + 7; const int infM = 0x3f3f3f3f; //a little bigger than 1e9 const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18 const int N = 100002; const int mod = 998244353; const ld eps = 1e-9; vector<int> g[N], gr[N], comp[N]; int tin[N], fup[N], T = 0, sz[N], n, m; ll ans = 0; void gfs(int v, int p) { sz[v] = 1; for (int to : g[v]) { if (to != p) { gfs(to, v); sz[v] += sz[to]; } } int siz = n - sz[v]; for (int to : g[v]) { if (to != p) { ans += siz * 1LL * sz[to]; siz += sz[to]; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a, --b; g[a].pb(b), g[b].pb(a); } for (int i = 0; i < n; ++i) { if (!sz[i]) { gfs(i, -1); } } cout << ans * 2; return 0; }
#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...