oj.uz

Submission #772000

# Submission time Handle Problem Language Result Execution time Memory
772000 2023-07-03T13:37:10 Z CyberCow Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
//#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const int N = 300005;
vector<ll> v[N];
ll sz[N];
ll color[N];
ll guyn = 0;
ll chap;
 
void Dfs(ll g)
{
    sz[g] = 1;
    color[g] = guyn;
    for (auto to : v[g])
    {
        if (color[to] == 0)
        {
            Dfs(to);
            sz[g] += sz[to];
        }
    }
}
 
ll koxqan = 0;
 
void Dfs1(ll g, ll guyn, int p)
{
    koxqan += sz[g] * (chap - sz[g]);
    for (auto to : v[g])
    {
        if (color[to] == guyn && to != p)
        {
            Dfs1(to, guyn, g);
        }
    }
}
 
void solve()
{
    ll n, i, j, x, y, m;
    cin >> n >> m;
    vector<pair<ll, ll>> kox;
    for ( i = 0; i < m; i++)
    {
        cin >> x >> y;
        kox.push_back({ x, y });
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ll ans = 0;
    for ( i = 1; i <= n; i++)
    {
        if (color[i] == 0)
        {
            koxqan = 0;
            guyn++;
            Dfs(i);
            chap = sz[i];
            Dfs1(i, guyn, -1);
            ans += koxqan - (chap * (chap - 1) / 2);
        }
    }
    cout << ans * 2;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:64:14: warning: unused variable 'j' [-Wunused-variable]
   64 |     ll n, i, j, x, y, m;
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 795716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7440 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7400 KB Output is correct
5 Correct 4 ms 7488 KB Output is correct
6 Correct 4 ms 7384 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7384 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7384 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7384 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 3 ms 7380 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15128 KB Output is correct
2 Correct 37 ms 15424 KB Output is correct
3 Correct 37 ms 15424 KB Output is correct
4 Correct 37 ms 15500 KB Output is correct
5 Correct 36 ms 15420 KB Output is correct
6 Correct 50 ms 18364 KB Output is correct
7 Correct 42 ms 17628 KB Output is correct
8 Correct 42 ms 17000 KB Output is correct
9 Correct 43 ms 16476 KB Output is correct
10 Correct 51 ms 15428 KB Output is correct
11 Correct 37 ms 15460 KB Output is correct
12 Correct 36 ms 15428 KB Output is correct
13 Correct 37 ms 15508 KB Output is correct
14 Correct 45 ms 15008 KB Output is correct
15 Correct 42 ms 14412 KB Output is correct
16 Correct 20 ms 12744 KB Output is correct
17 Correct 27 ms 15676 KB Output is correct
18 Correct 27 ms 15648 KB Output is correct
19 Correct 28 ms 16324 KB Output is correct
20 Correct 29 ms 15736 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Runtime error 477 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15420 KB Output is correct
2 Correct 42 ms 15320 KB Output is correct
3 Runtime error 580 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -