Submission #1106827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106827	2024-10-31T07:15:46 Z	mispertion	Duathlon (APIO18_duathlon)	C++17	0 / 100	312 ms	76836 KB

count_triplets

#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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	33360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	33360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	33360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	33360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #1106827

Compilation message