oj.uz

답안 #1106827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106827 2024-10-31T07:15:46 Z mispertion 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 312 ms 76836 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second

const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 2e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) {
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}


ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

int n, m, tin[N], used[N], low[N], cnt[N], cur, tick, art[N], sz[N], dp[N], ndp[N];
vector<int> g[N];
vector<int> ng[N];

void dfs(int v, int p){
    tin[v] = ++tick;
    low[v] = tin[v];
    used[v] = 1;
    int ch = 0;
    bool isart = false;
    for(auto u : g[v]){
        if(u == p) continue;
        if(used[u]){
            low[v] = min(low[v], tin[u]);
        }else{
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            ch++;
            if(p != 0 && low[u] >= tin[v])
                isart = true;
        }
    }
    if(p == 0 && ch > 1)
        isart = true;
    if(isart)
        art[v] = 1;
}

map<pii, int> mp;

void dfs1(int v, int c){
    used[v] = 1;
    if(c == 0){
        for(auto u : g[v]){
            if(used[u]) continue;
            cur++;
            mp[{u, v}] = cur;
            mp[{v, u}] = cur;
            dfs1(u, cur);
        }
        return;
    }
    for(auto u : g[v]){
        if(used[u]){
            if(tin[u] < tin[v]){
                mp[{u, v}] = c;
                mp[{v, u}] = c;
            }
            continue;
        }
        if(low[u] >= tin[v]){
            cur++;
            mp[{u, v}] = cur;
            mp[{v, u}] = cur;
            dfs1(u, cur);
        }else{
            mp[{u, v}] = c;
            mp[{v, u}] = c;
            dfs1(u, c);
        }
    }
}

void dfs2(int v, int p){
    used[v] = 1;
    if(v <= n){
        sz[v] = 1;
    }else{
        dp[v] = cnt[v - n] * (cnt[v - n] - 1);
        sz[v] = cnt[v - n];
    }
    int cur = 0;
    for(auto u : ng[v]){
        if(u == p) continue;
        dfs2(u, v);
        sz[v] += sz[u];
        if(v > n){
            dp[v] += 2 * cnt[v - n] * sz[u];
            dp[v] += 2 * cur * sz[u];
            cur += sz[u];
        }
    }
}

void dfs3(int v, int p){
    used[v] = 1;
    if(v > n){
        int csm = (cnt[v - n]) * (cnt[v - n] - 1) / 2 + (n - sz[v]) * (cnt[v - n]);
        int cs = n - sz[v];
        for(auto u : ng[v]){
            if(u == p) continue;
            csm += (sz[u] * cnt[v - n]);
            csm += (cs * sz[u]);
            cs += sz[u];
        }
        for(auto u : ng[v]){
            if(u == p) continue;
            csm -= (sz[u] * cnt[v - n]);
            csm -= (sz[u] * (cs - sz[u]));
            ndp[u] = csm * 2;
            csm += (sz[u] * cnt[v - n]);
            csm += (sz[u] * (cs - sz[u]));
            dfs3(u, v);
        }
    }else{
        for(auto u : ng[v]){
            if(u != p)
                dfs3(u, v);
        }
    }
}

int ans = 0;
void dfs4(int v, int p){
    used[v] = 1;
    if(v <= n){
        ans += ndp[v];
        int cs = n - sz[v];
        for(auto u : ng[v]){
            if(u == p) continue;
            ans += dp[u];
            ans += 2 * sz[u] * cs;
            cs += sz[u];
        }
    }else{
        ans += cnt[v - n] * (cnt[v - n] - 1) * (cnt[v - n] - 2);
        int cs = n - sz[v];
        ans += 2 * (cnt[v - n] * (cnt[v - n] - 1) * (n - sz[v]));
        for(auto u : ng[v]){
            if(u == p) continue;
            ans += 2 * (cnt[v - n] * (cnt[v - n] - 1) * sz[u]);
            ans += (cnt[v - n] * (2 * (cs * sz[u])));
            cs += sz[u];
        }
    }
    for(auto u : ng[v]){
        if(u == p) continue;
        dfs4(u, v);
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(!used[i])
            dfs(i, 0);
    }
    for(int i = 1; i <= n; i++)
        used[i] = 0;
    for(int i = 1; i <= n; i++)
        if(!used[i])
            dfs1(i, 0);
    for(int i = 1; i <= n; i++){
        if(art[i]){
            for(auto e : g[i]){
                ng[i].push_back(n + mp[{i, e}]);
                ng[n + mp[{i, e}]].push_back(i);
            }
            sort(ng[i].begin(), ng[i].end());
            ng[i].resize(unique(ng[i].begin(), ng[i].end()) - ng[i].begin());
        }else{
            if(g[i].size() > 0){
                cnt[mp[{g[i][0], i}]]++;
            }
        }
    }
    for(int i = n + 1; i <= n + cur; i++){
        ng[i].resize(unique(ng[i].begin(), ng[i].end()) - ng[i].begin());
    }
    for(int i = n + 1; i <= n + cur; i++){
        if(!used[i])
            dfs2(i, 0);
    }
    for(int i = 1; i <= n + cur; i++)
        used[i] = 0;
    for(int i = n + 1; i <= n + cur; i++){
        if(!used[i])
            dfs3(i, 0);
    }
    for(int i = 1; i <= n + cur; i++)
        used[i] = 0;
    for(int i = n + 1; i <= n + cur; i++){
        if(!used[i])
            dfs4(i, 0);
    }
    for(int i = 1; i <= n + cur; i++)
        used[i] = 0;
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 69216 KB Output is correct
2 Correct 221 ms 69192 KB Output is correct
3 Incorrect 222 ms 69704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 67912 KB Output is correct
2 Correct 214 ms 67912 KB Output is correct
3 Correct 226 ms 67912 KB Output is correct
4 Correct 213 ms 67912 KB Output is correct
5 Correct 216 ms 67912 KB Output is correct
6 Correct 246 ms 76836 KB Output is correct
7 Correct 263 ms 74084 KB Output is correct
8 Correct 256 ms 72652 KB Output is correct
9 Correct 230 ms 70884 KB Output is correct
10 Incorrect 218 ms 67912 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 35664 KB Output is correct
2 Correct 7 ms 35664 KB Output is correct
3 Correct 7 ms 35664 KB Output is correct
4 Correct 7 ms 35664 KB Output is correct
5 Correct 7 ms 35664 KB Output is correct
6 Correct 7 ms 35712 KB Output is correct
7 Correct 7 ms 35664 KB Output is correct
8 Correct 8 ms 35664 KB Output is correct
9 Correct 6 ms 35916 KB Output is correct
10 Correct 8 ms 35712 KB Output is correct
11 Correct 7 ms 35508 KB Output is correct
12 Correct 8 ms 35832 KB Output is correct
13 Correct 9 ms 35664 KB Output is correct
14 Correct 8 ms 35664 KB Output is correct
15 Correct 7 ms 35664 KB Output is correct
16 Incorrect 10 ms 35932 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 67928 KB Output is correct
2 Correct 220 ms 68164 KB Output is correct
3 Correct 220 ms 68192 KB Output is correct
4 Correct 216 ms 67144 KB Output is correct
5 Correct 197 ms 64616 KB Output is correct
6 Correct 210 ms 63304 KB Output is correct
7 Correct 204 ms 62424 KB Output is correct
8 Correct 159 ms 61512 KB Output is correct
9 Correct 192 ms 60904 KB Output is correct
10 Correct 163 ms 60616 KB Output is correct
11 Correct 166 ms 60064 KB Output is correct
12 Correct 163 ms 57672 KB Output is correct
13 Correct 157 ms 57928 KB Output is correct
14 Correct 163 ms 61000 KB Output is correct
15 Correct 312 ms 74360 KB Output is correct
16 Correct 281 ms 72204 KB Output is correct
17 Correct 301 ms 73492 KB Output is correct
18 Correct 295 ms 71496 KB Output is correct
19 Incorrect 254 ms 67344 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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