oj.uz

답안 #886733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886733 2023-12-12T18:11:49 Z Kutan 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 96 ms 41420 KB 
// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
 
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));
 
const int INF = 1e9 , mod = 1e9 + 7;
 
template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }
 
template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}
 
template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }
 
template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }
 
template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }
 
template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }
 
#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}
 
typedef long long ll;
typedef double db;
const int N = 2e5 + 5;
 
int n, m;
vi adj[N], g[N * 2];
int num[N], low[N], timeDfs(0), numNode;
int f[N*2], sz[N*2], totsize;
stack<int> st;
ll res = 0;
 
void readip(){
    cin >> n >> m;
    REP(i, 1, m) {
        int u, v; cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
}
 
namespace sub3{
    bool check() {
        REP(i, 1, n) if (adj[i].size() > 2) return false;
        return true;
    }
 
    vector<bool> vis;
    int numNode = 0;
 
    void dfs(int u) {
        ++numNode;
        vis[u] = true;
        for (int v : adj[u]) if (!vis[v])
            dfs(v);
    }
 
    void solve() {
        ll res = 0;
        vis.assign(n + 2, 0);
        REP(i, 1, n) if (!vis[i] && adj[i].size() == 1) {
            numNode = 0;
            dfs(i);
            res += 1LL * numNode * (numNode - 1) * (numNode - 2) / 3;
        }
        REP(i, 1, n) if (!vis[i] && adj[i].size() == 2) {
            numNode = 0;
            dfs(i);
            res += 1LL * numNode * (numNode - 1) * (numNode - 2);
        }
        cout << res << ln;
    }   
};
 
namespace sub5{
    vector<bool> vis;
    bool oke = 1;
    void dfs(int u, int p) {
        if (!oke) return;
        vis[u] = 1;
        for (int v : adj[u]) if (v != p) {
            if (vis[v]) {
                oke = 0;
                return;
            }
            dfs(v, u);
        }
    }
 
    bool check() {
        vis.assign(n + 2, 0);
        REP(i, 1, n) if (!vis[i]) dfs(i, -1);
        return oke;
    }
 
    ll res = 0;
    int cnt = 0;
    vector<int> sz, mark, Size;
    void dfs_tree(int u, int p) {
        mark[u] = cnt;
        sz[u] = 0;
        for (int v : adj[u]) if (v != p) {
            dfs_tree(v, u);
            res += 2LL * sz[u] * sz[v];
            sz[u] += sz[v];
        }
        ++sz[u];
    }
 
    void solve() {
        sz.assign(n + 2, 0);
        mark.assign(n + 2, -1);
        REP(i, 1, n) if (mark[i] == -1) {
            dfs_tree(i, -1);
            Size.eb(sz[i]);
            ++cnt;
        }
        REP(i, 1, n) {
            res += 2LL * (sz[i] - 1) * (Size[mark[i]] - sz[i]);
        }
        cout << res << ln;
    }
};
 
namespace subfull {
    struct DSU{
        int par[N], sz[N];
        int root(int x) {
            if (x == par[x]) return x;
            return par[x] = root(par[x]);
        }
 
        void unite(int u, int v) {
            u = root(u) , v = root(v);
            if (u == v) return;
            if (sz[u] < sz[v]) swap(u, v);
            sz[u] += sz[v];
            par[v] = u;
        }
 
        void process() {
            REP(i, 1, n) par[i] = i, sz[i] = 1;
            REP(u, 1, n) for (int v : adj[u]) 
                unite(u, v);
        }
    } dsu;
 
    void add_edge(int u, int v) {
        g[u].eb(v);
        g[v].eb(u);
        // cout << u << ' ' << v << ln;
    }
 
    void dfs(int u) {
        num[u] = low[u] = ++timeDfs;
        st.push(u);
        for (int v : adj[u]) {
            if (num[v]) minimize(low[u], num[v]);
            else {
                dfs(v);
                minimize(low[u], low[v]);
                if (num[u] == low[v]) {
                    ++numNode;
                    add_edge(u, numNode);
                    int x = -1, cnt(0);  
                    do {
                        x = st.top();
                        st.pop();
                        add_edge(x, numNode);
                        ++cnt;
                    } while(x != v) ;
 
                    f[numNode] = cnt;
                    /// case 1: s, c, f in one biconnected component
                    res += 1LL * (cnt + 1) * (cnt) * (cnt - 1);
                    /// case 2: 2 vertices in one biconnected component, and the remain vertex in another one.
                    res += 2LL * cnt * (cnt - 1) * (dsu.sz[dsu.root(u)] - cnt - 1);
                }
            }
        }
    }
 
    void dfs_tree(int u, int p) {
        sz[u] = 0;
        for (int v : g[u]) if (v != p) {
            dfs_tree(v, u);
            if (u <= n) {
                res += 2LL * sz[u] * sz[v];
                // cout << u << ' ' << 2LL * sz[u] * sz[v] << ln;
                sz[u] += sz[v];
            }
            else {
                // cout << u << ' ' << 2LL * f[u] * sz[u] * (sz[v] - 1) << ln;
                res += 2LL * f[u] * sz[u] * (sz[v] - 1);  
                sz[u] += sz[v] - 1;
                res -= 2LL * (sz[v] - 1) * (f[u] - 1);
            }
        }
 
        if (u <= n) ++sz[u];    
        else sz[u] += f[u];
 
        // if (u <= n) {
            // res += 2LL * (totsize - sz[u]) * (sz[u] - 1);
            // cout << u << ' ' << 2LL * (totsize - sz[u]) * (sz[u] - 1) << ln;
        // }
        // else {}
 
        if (u > n) {
            res += 2LL * (totsize - sz[u]) * f[u] * (sz[u] - f[u]);
            // cout << u << ' ' <<  2LL * (totsize - sz[u]) * f[u] * (sz[u] - f[u])  << ln;
        }
    }
 
    void solve() {
        numNode = n;
        dsu.process();
        REP(i, 1, n) if (dsu.root(i) == i) {
            totsize = dsu.sz[i];
            dfs(i);
            dfs_tree(i, -1);
        }
        cout << res << ln;
    }
};
 
void solve(){       
    // if (sub3::check()) {
    //     sub3::solve();
    //     return;
    // }
    // if (sub5::check()) {
    //     sub5::solve();
    //     return;
    // }
 
    subfull::solve();
}
 
int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

count_triplets.cpp: In function 'void readip()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:148:5: note: in expansion of macro 'REP'
  148 |     REP(i, 1, m) {
      |     ^~~
count_triplets.cpp: In function 'bool sub3::check()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:157:9: note: in expansion of macro 'REP'
  157 |         REP(i, 1, n) if (adj[i].size() > 2) return false;
      |         ^~~
count_triplets.cpp: In function 'void sub3::solve()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:174:9: note: in expansion of macro 'REP'
  174 |         REP(i, 1, n) if (!vis[i] && adj[i].size() == 1) {
      |         ^~~
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:179:9: note: in expansion of macro 'REP'
  179 |         REP(i, 1, n) if (!vis[i] && adj[i].size() == 2) {
      |         ^~~
count_triplets.cpp: In function 'bool sub5::check()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:205:9: note: in expansion of macro 'REP'
  205 |         REP(i, 1, n) if (!vis[i]) dfs(i, -1);
      |         ^~~
count_triplets.cpp: In function 'void sub5::solve()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:226:9: note: in expansion of macro 'REP'
  226 |         REP(i, 1, n) if (mark[i] == -1) {
      |         ^~~
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:231:9: note: in expansion of macro 'REP'
  231 |         REP(i, 1, n) {
      |         ^~~
count_triplets.cpp: In member function 'void subfull::DSU::process()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:255:13: note: in expansion of macro 'REP'
  255 |             REP(i, 1, n) par[i] = i, sz[i] = 1;
      |             ^~~
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'u' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:256:13: note: in expansion of macro 'REP'
  256 |             REP(u, 1, n) for (int v : adj[u])
      |             ^~~
count_triplets.cpp: In function 'void subfull::solve()':
count_triplets.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
count_triplets.cpp:331:9: note: in expansion of macro 'REP'
  331 |         REP(i, 1, n) if (dsu.root(i) == i) {
      |         ^~~
count_triplets.cpp: In function 'void file()':
count_triplets.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20572 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 6 ms 20572 KB Output is correct
4 Correct 5 ms 20572 KB Output is correct
5 Correct 4 ms 20572 KB Output is correct
6 Correct 5 ms 20596 KB Output is correct
7 Incorrect 5 ms 20592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20572 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 6 ms 20572 KB Output is correct
4 Correct 5 ms 20572 KB Output is correct
5 Correct 4 ms 20572 KB Output is correct
6 Correct 5 ms 20596 KB Output is correct
7 Incorrect 5 ms 20592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 41420 KB Output is correct
2 Correct 69 ms 41316 KB Output is correct
3 Correct 77 ms 35772 KB Output is correct
4 Correct 62 ms 38500 KB Output is correct
5 Correct 87 ms 33080 KB Output is correct
6 Correct 85 ms 37104 KB Output is correct
7 Correct 63 ms 31828 KB Output is correct
8 Correct 77 ms 32980 KB Output is correct
9 Correct 79 ms 30500 KB Output is correct
10 Correct 63 ms 31488 KB Output is correct
11 Correct 43 ms 28500 KB Output is correct
12 Correct 45 ms 28240 KB Output is correct
13 Correct 49 ms 28252 KB Output is correct
14 Correct 44 ms 27984 KB Output is correct
15 Correct 37 ms 27224 KB Output is correct
16 Correct 46 ms 26960 KB Output is correct
17 Correct 8 ms 21104 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 6 ms 21084 KB Output is correct
20 Correct 6 ms 21336 KB Output is correct
21 Correct 6 ms 21084 KB Output is correct
22 Correct 6 ms 21084 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20740 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct
3 Correct 5 ms 20572 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 6 ms 20812 KB Output is correct
6 Correct 5 ms 20572 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 6 ms 20572 KB Output is correct
9 Correct 4 ms 20572 KB Output is correct
10 Correct 5 ms 20568 KB Output is correct
11 Correct 5 ms 20572 KB Output is correct
12 Correct 5 ms 20572 KB Output is correct
13 Correct 5 ms 20572 KB Output is correct
14 Correct 6 ms 20572 KB Output is correct
15 Correct 5 ms 20568 KB Output is correct
16 Correct 5 ms 20568 KB Output is correct
17 Correct 5 ms 20572 KB Output is correct
18 Correct 5 ms 20756 KB Output is correct
19 Correct 5 ms 20596 KB Output is correct
20 Correct 6 ms 20572 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 30232 KB Output is correct
2 Correct 67 ms 30292 KB Output is correct
3 Correct 67 ms 30292 KB Output is correct
4 Correct 90 ms 30392 KB Output is correct
5 Correct 93 ms 30404 KB Output is correct
6 Correct 76 ms 37932 KB Output is correct
7 Correct 70 ms 36692 KB Output is correct
8 Correct 65 ms 34216 KB Output is correct
9 Correct 75 ms 32592 KB Output is correct
10 Correct 70 ms 30260 KB Output is correct
11 Correct 68 ms 30396 KB Output is correct
12 Correct 71 ms 30292 KB Output is correct
13 Correct 73 ms 30380 KB Output is correct
14 Correct 54 ms 29780 KB Output is correct
15 Correct 69 ms 29264 KB Output is correct
16 Correct 39 ms 27100 KB Output is correct
17 Correct 65 ms 30924 KB Output is correct
18 Correct 61 ms 30728 KB Output is correct
19 Correct 55 ms 30920 KB Output is correct
20 Correct 47 ms 30840 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct
3 Incorrect 5 ms 20572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 30380 KB Output is correct
2 Correct 96 ms 30308 KB Output is correct
3 Incorrect 68 ms 29708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20572 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 6 ms 20572 KB Output is correct
4 Correct 5 ms 20572 KB Output is correct
5 Correct 4 ms 20572 KB Output is correct
6 Correct 5 ms 20596 KB Output is correct
7 Incorrect 5 ms 20592 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20572 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 6 ms 20572 KB Output is correct
4 Correct 5 ms 20572 KB Output is correct
5 Correct 4 ms 20572 KB Output is correct
6 Correct 5 ms 20596 KB Output is correct
7 Incorrect 5 ms 20592 KB Output isn't correct
8 Halted 0 ms 0 KB -