oj.uz

답안 #626001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626001 2022-08-11T06:11:35 Z Do_you_copy 철인 이종 경기 (APIO18_duathlon) C++17
8 / 100
 228 ms 31996 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
int n, m;
int low[maxN];
int num[maxN];
bool onstack[maxN];
bool visited[maxN];
int timedfs;
int id[maxN];
int scc;
vector <vector <int>> adj;
vector <vector <int>> adj1;
vector <int> S;

void pre_dfs(int u, int p){
    low[u] = num[u] = ++timedfs;
    S.pb(u);
    onstack[u] = 1;
    visited[u] = 1;
    for (int i: adj[u]){
        if (i == p) continue;
        if (!visited[i]){
            pre_dfs(i, u);
            low[u] = min(low[u], low[i]);
        }
        else if(onstack[i]){
            low[u] = min(low[u], num[i]);
        }
    }
    if (low[u] == num[u]){
        ++scc;
        int v;
        do{
            v = S.back();
            S.pop_back();
            id[v] = scc;
            onstack[v] = 0;
        } while (v != u);
    }
}

map <pii, bool> mp;

ll ans = 0;
bool vis[maxN];
int sz[maxN];
int child[maxN];
ll sumchild[maxN];
ll sumsz[maxN];

inline ll calc(ll x){
    return x * (x - 1) * (x - 2) / 2;
}

inline ll cal(ll x){
    return x * x;
}

void dfs(int u, int total_sz = 0){
    vis[u] = 1;
    ans += total_sz * cal(sz[u] - 1);
    for (int i: adj1[u]){
        if (vis[i]) continue;
        dfs(i, total_sz + sz[u]);
        child[u] += child[i] + 1;
        sumsz[u] += sumsz[i];
        sumchild[u] += sumchild[i];
        ans += sumsz[i] * cal(sz[u] - 1);
    }
    ans += sumchild[u];
    sumchild[u] += child[u];
    sumsz[u] += sz[u];
    ans += calc(sz[u]);
}

void Init(){
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 1; i <= n; ++i){
        if (!visited[i]){
            pre_dfs(i, i);
        }
    }
    adj1.resize(scc + 1);
    for (int i = 1; i <= n; ++i){
        ++sz[id[i]];
        for (int j: adj[i]){
            if (id[i] != id[j] && !mp[{id[i], id[j]}]){
                mp[{id[i], id[j]}] = 1;
                mp[{id[j], id[i]}] = 1;
                adj1[id[i]].pb(id[j]);
                adj1[id[j]].pb(id[i]);
            }
        }
    }
    for (int i = 1; i <= scc; ++i){
        if (!vis[i]){
            dfs(i);
        }
    }
    cout << ans * 2;
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 18452 KB Output is correct
2 Correct 60 ms 18264 KB Output is correct
3 Correct 123 ms 24644 KB Output is correct
4 Correct 76 ms 21288 KB Output is correct
5 Correct 119 ms 19556 KB Output is correct
6 Correct 137 ms 25996 KB Output is correct
7 Correct 134 ms 24140 KB Output is correct
8 Correct 131 ms 25388 KB Output is correct
9 Correct 148 ms 23260 KB Output is correct
10 Correct 164 ms 21840 KB Output is correct
11 Correct 88 ms 19468 KB Output is correct
12 Correct 86 ms 19528 KB Output is correct
13 Correct 76 ms 19620 KB Output is correct
14 Correct 91 ms 19276 KB Output is correct
15 Correct 62 ms 19296 KB Output is correct
16 Correct 62 ms 18636 KB Output is correct
17 Correct 7 ms 10452 KB Output is correct
18 Correct 7 ms 10460 KB Output is correct
19 Correct 8 ms 10440 KB Output is correct
20 Correct 7 ms 10404 KB Output is correct
21 Correct 7 ms 10332 KB Output is correct
22 Correct 8 ms 10324 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 31996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 228 ms 31952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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