oj.uz

답안 #886740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886740 2023-12-12T18:22:33 Z Kutan 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 87 ms 38376 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];
                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 * (f[u] - 1) * (f[u] - 2) * (sz[v] - 1);
            }
        }
 
        if (u <= n) ++sz[u];    
        else sz[u] += f[u];
 
        if (u > n) {
            res += 2LL * (totsize - sz[u]) * f[u] * (sz[u] - f[u]);
            res += 2LL * (f[u]) * (f[u] - 1) * (totsize - sz[u] - 1);
        }
    }
 
    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:324:9: note: in expansion of macro 'REP'
  324 |         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 5 ms 20572 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 4 ms 20568 KB Output is correct
4 Correct 4 ms 20572 KB Output is correct
5 Correct 4 ms 20572 KB Output is correct
6 Correct 4 ms 20592 KB Output is correct
7 Incorrect 6 ms 20572 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 38376 KB Output is correct
2 Correct 58 ms 38268 KB Output is correct
3 Correct 76 ms 34128 KB Output is correct
4 Correct 55 ms 36296 KB Output is correct
5 Correct 67 ms 32716 KB Output is correct
6 Correct 62 ms 37324 KB Output is correct
7 Correct 57 ms 31596 KB Output is correct
8 Correct 58 ms 32336 KB Output is correct
9 Correct 87 ms 30220 KB Output is correct
10 Correct 75 ms 30800 KB Output is correct
11 Correct 45 ms 28552 KB Output is correct
12 Correct 44 ms 28496 KB Output is correct
13 Correct 41 ms 28368 KB Output is correct
14 Correct 43 ms 27984 KB Output is correct
15 Correct 43 ms 27448 KB Output is correct
16 Correct 35 ms 26960 KB Output is correct
17 Correct 7 ms 21084 KB Output is correct
18 Correct 6 ms 21084 KB Output is correct
19 Correct 7 ms 21084 KB Output is correct
20 Correct 6 ms 21084 KB Output is correct
21 Correct 6 ms 21148 KB Output is correct
22 Correct 6 ms 21128 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20572 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 20608 KB Output is correct
5 Correct 5 ms 20572 KB Output is correct
6 Correct 5 ms 20572 KB Output is correct
7 Correct 5 ms 20828 KB Output is correct
8 Correct 5 ms 20572 KB Output is correct
9 Correct 5 ms 20572 KB Output is correct
10 Correct 5 ms 20572 KB Output is correct
11 Correct 5 ms 20740 KB Output is correct
12 Correct 5 ms 20572 KB Output is correct
13 Correct 5 ms 20572 KB Output is correct
14 Correct 5 ms 20572 KB Output is correct
15 Correct 5 ms 20568 KB Output is correct
16 Correct 5 ms 20572 KB Output is correct
17 Correct 5 ms 20572 KB Output is correct
18 Correct 6 ms 20572 KB Output is correct
19 Correct 4 ms 20572 KB Output is correct
20 Correct 4 ms 20572 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 30164 KB Output is correct
2 Correct 66 ms 30364 KB Output is correct
3 Correct 60 ms 30288 KB Output is correct
4 Correct 65 ms 30288 KB Output is correct
5 Correct 76 ms 30156 KB Output is correct
6 Correct 75 ms 37972 KB Output is correct
7 Correct 74 ms 36464 KB Output is correct
8 Correct 74 ms 34064 KB Output is correct
9 Correct 79 ms 32612 KB Output is correct
10 Correct 63 ms 30192 KB Output is correct
11 Correct 60 ms 30288 KB Output is correct
12 Correct 78 ms 30268 KB Output is correct
13 Correct 66 ms 30216 KB Output is correct
14 Correct 52 ms 29780 KB Output is correct
15 Correct 46 ms 29264 KB Output is correct
16 Correct 41 ms 27220 KB Output is correct
17 Correct 50 ms 31000 KB Output is correct
18 Correct 44 ms 30792 KB Output is correct
19 Correct 58 ms 30856 KB Output is correct
20 Correct 45 ms 30800 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20572 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 63 ms 30284 KB Output is correct
2 Correct 60 ms 30292 KB Output is correct
3 Incorrect 75 ms 29520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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