oj.uz

답안 #64859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64859 2018-08-06T00:06:53 Z qkxwsm 철인 이종 경기 (APIO18_duathlon) C++17
66 / 100
 355 ms 48108 KB 
/*
PROG: source
LANG: C++11
_____
.'     '.
/  0   0  \
|     ^     |
|  \     /  |
\  '---'  /
'._____.'
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
        int operator()(int x) const
        {
                x ^= (x >> 20) ^ (x >> 12);
                return x ^ (x >> 7) ^ (x >> 4);
        }
        int operator()(long long x) const
        {
                return x ^ (x >> 32);
        }
};

template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using hashtable = gp_hash_table<T, T, chash>;

template<class T>
void readi(T &x)
{
        T input = 0;
        bool negative = false;
        char c = ' ';
        while (c < '-')
        {
                c = getchar();
        }
        if (c == '-')
        {
                negative = true;
                c = getchar();
        }
        while (c >= '0')
        {
                input = input * 10 + (c - '0');
                c = getchar();
        }
        if (negative)
        {
                input = -input;
        }
        x = input;
}
template<class T>
void printi(T output)
{
        if (output == 0)
        {
                putchar('0');
                return;
        }
        if (output < 0)
        {
                putchar('-');
                output = -output;
        }
        int aout[20];
        int ilen = 0;
        while(output)
        {
                aout[ilen] = ((output % 10));
                output /= 10;
                ilen++;
        }
        for (int i = ilen - 1; i >= 0; i--)
        {
                putchar(aout[i] + '0');
        }
        return;
}
template<class T>
void ckmin(T &a, T b)
{
        a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
        a = max(a, b);
}
template<class T>
T normalize(T x, T mod = 1000000007)
{
        return (((x % mod) + mod) % mod);
}
long long randomizell(long long mod)
{
        return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
int randomize(int mod)
{
        return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

int N, M, T, K;
vector<int> edge[MAXN], edge1[MAXN];
int sz[MAXN];
vector<pii> bridge;
vector<pii> edges;
bool ap[MAXN];
vector<int> bcc[MAXN];
int id[MAXN], aid[MAXN];
int parent[MAXN];
int subtree[MAXN];
int disc[MAXN], low[MAXN];
int dsu[MAXN], dsz[MAXN];
vector<int> nodes[MAXN];
bool seen[MAXN];
ll ans = 0, tot = 0;

int find_parent(int u)
{
        return (u == dsu[u] ? u : dsu[u] = find_parent(dsu[u]));
}
void merge(int u, int v)
{
        u = find_parent(u);
        v = find_parent(v);
        if (u == v) return;
        if (dsz[u] > dsz[v])
        {
                swap(u, v);
        }
        dsz[v] += dsz[u];
        dsz[u] = 0;
        dsu[u] = v;
        return;
}
void dfs(int u, bool head = false)
{
        disc[u] = T;
        low[u] = T;
        seen[u] = true;
        T++;
        int children = 0;
        for (int v : edge[u])
        {
                if (v == parent[u])
                {
                        continue;
                }
                if (seen[v])
                {
                        ckmin(low[u], low[v]);
                        continue;
                }
                children++;
                parent[v] = u;
                edges.PB({u, v});
                dfs(v);
                ckmin(low[u], low[v]);
                if (low[v] >= disc[u])
                {
                        if (low[v] != disc[u])
                        {
                                bridge.PB({u, v});
                        }
                        if (!head)
                        {
                                ap[u] = true;
                                while(edges.back() != MP(u, v))
                                {
                                        bcc[K].PB(edges.back().fi);
                                        bcc[K].PB(edges.back().se);
                                        edges.pop_back();
                                }
                                bcc[K].PB(edges.back().fi);
                                bcc[K].PB(edges.back().se);
                                edges.pop_back();
                                K++;
                        }
                }
                if (head)
                {
                        if (children > 1)
                        {
                                ap[u] = true;
                        }
                        while(edges.back() != MP(u, v))
                        {
                                bcc[K].PB(edges.back().fi);
                                bcc[K].PB(edges.back().se);
                                edges.pop_back();
                        }
                        bcc[K].PB(edges.back().fi);
                        bcc[K].PB(edges.back().se);
                        edges.pop_back();
                        K++;
                }
        }
}
void dfs1(int u)
{
        subtree[u] = sz[u];
        for (int v : edge1[u])
        {
                if (v == parent[u])
                {
                        continue;
                }
                parent[v] = u;
                dfs1(v);
                subtree[u] += subtree[v];
        }
        return;
}

int32_t main()
{
        ios_base::sync_with_stdio(0);
        srand(time(0));
        //	cout << fixed << setprecision(10);
        //	cerr << fixed << setprecision(10);
        if (fopen("input.in", "r"))
        {
                freopen ("input.in", "r", stdin);
                freopen ("output.out", "w", stdout);
        }
        cin >> N >> M;
        for (int i = 0; i < N; i++)
        {
                dsu[i] = i;
                dsz[i] = i;
        }
        for (int i = 0; i < M; i++)
        {
                int u, v;
                cin >> u >> v;
                u--; v--;
                edge[u].PB(v);
                edge[v].PB(u);
                merge(u, v);
        }
        for (int i = 0; i < N; i++)
        {
                parent[i] = N;
        }
        for (int i = 0; i < N; i++)
        {
                nodes[find_parent(i)].PB(i);
        }
        for (int cc = 0; cc < N; cc++)
        {
                if (find_parent(cc) != cc)
                {
                        continue;
                }
                int n = nodes[cc].size();
                dfs(cc, 1);
                for (int i = 0; i < K; i++)
                {
                        sort(bcc[i].begin(), bcc[i].end());
                        bcc[i].erase(unique(bcc[i].begin(), bcc[i].end()), bcc[i].end());
                        // cerr << "bcc # " << i << ":";
                        for (int u : bcc[i])
                        {
                                // cerr << ' ' << u;
                                id[u] = i;
                                if (!ap[u])
                                {
                                        sz[i]++;
                                }
                        }
                        // cerr << endl;
                }
                for (int i = 0; i < n; i++)
                {
                        int u = nodes[cc][i];
                        if (ap[u])
                        {
                                aid[u] = K;
                                sz[K] = 1;
                                K++;
                                // cerr << "ap " << i << " id " << K - 1 << endl;
                        }
                }
                for (int i = 0; i < K; i++)
                {
                        // cerr << "bcc " << i << ":";
                        for (int u : bcc[i])
                        {
                                // cerr << ' ' << u;
                                if (ap[u])
                                {
                                        edge1[i].PB(aid[u]);
                                        edge1[aid[u]].PB(i);
                                }
                        }
                        // cerr << endl;
                }
                // for (int i = 0; i < K; i++)
                // {
                //         for (int u : edge1[i])
                //         {
                //                 if (i <= u) cerr << i << " -> " << u << endl;
                //         }
                // }
                // for (int i = 0; i < K; i++)
                // {
                //         cerr << sz[i] << ' ';
                // }
                // cerr << endl;
                for (int i = 0; i < K; i++)
                {
                        parent[i] = K;
                }
                dfs1(0);
                //all 3 distinct blocks
                //the only violations allowed are: guy -> ap in u -> u
                for (int i = 0; i < K; i++)
                {
                        tot += 1ll * (n - sz[i]) * sz[i] * (n - sz[i] - 1);
                        if (bcc[i].empty())
                        {
                                for (int v : edge1[i])
                                {
                                        for (int w : edge1[v])
                                        {
                                                if (w == i) continue;
                                                if (w == parent[v]) continue;
                                                // if (i == 4) cerr << w << 'X' << v << endl;
                                                tot -= 1ll * subtree[w] * (subtree[w] - 1);
                                        }
                                        // tot -= 1ll * (n - subtree[parent[v]]) * (n - subtree[parent[v]] - 1);
                                }
                                tot -= 1ll * (n - subtree[parent[i]]) * (n - subtree[parent[i]] - 1);
                        }
                        else
                        {
                                for (int v : edge1[i])
                                {
                                        if (v == parent[i]) continue;
                                        tot -= 1ll * sz[i] * (subtree[v]) * (subtree[v] - 1);
                                }
                                tot -= 1ll * sz[i] * (n - subtree[i]) * (n - subtree[i] - 1);
                        }
                        // cerr << "after center " << i << " get " << tot << endl;
                        // tot += 2ll * sz[i] * (n - subtree[i]) * (subtree[i] - sz[i]);
                }
                // debug(tot);
                //three equal guys
                for (int i = 0; i < K; i++)
                {
                        tot += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2);
                }
                // debug(tot);
                //a=b or b=c BUT NOT BOTH!
                for (int i = 0; i < K; i++)
                {
                        tot += 2ll * sz[i] * (sz[i] - 1) * (n - sz[i]);
                }
                // debug(tot);
                if (sz[0] == n)
                {
                        ans += 1ll * n * (n - 1) * (n - 2);
                }
                else
                {
                        ans += tot;
                }
                for (int i = 0; i < K; i++)
                {
                        bcc[i].clear();
                        sz[i] = 0;
                        edge1[i].clear();
                        subtree[i] = 0;
                }
                K = 0; T = 0; tot = 0;
        }
        // for (int i = 0; i < K; i++)
        // {
        //     for (int v : edge1[i])
        //     {
        //         cerr << i << "->" << v << endl;
        //     }
        //     cerr << "size " << i << " = " << sz[i] << endl;
        // }
        // for (int i = 0; i < K; i++)
        // {
        //         cerr << "subtree " << i << "=" << subtree[i] << endl;
        // }
        //if a -> b must pass through c, then: a -> b -> c is bad; c -> b -> a is bad, c -> a -> b is bad, b -> a -> c
        //three separate components
        cout << ans << '\n';
        //	cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
        return 0;
}

Compilation message

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:264:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
                 freopen ("input.in", "r", stdin);
                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:265:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
                 freopen ("output.out", "w", stdout);
                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19248 KB Output is correct
3 Correct 20 ms 19248 KB Output is correct
4 Correct 20 ms 19296 KB Output is correct
5 Correct 18 ms 19296 KB Output is correct
6 Correct 22 ms 19336 KB Output is correct
7 Correct 24 ms 19340 KB Output is correct
8 Correct 30 ms 19340 KB Output is correct
9 Correct 20 ms 19340 KB Output is correct
10 Correct 25 ms 19508 KB Output is correct
11 Correct 21 ms 19508 KB Output is correct
12 Correct 20 ms 19508 KB Output is correct
13 Correct 22 ms 19508 KB Output is correct
14 Correct 19 ms 19508 KB Output is correct
15 Incorrect 19 ms 19508 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19248 KB Output is correct
3 Correct 20 ms 19248 KB Output is correct
4 Correct 20 ms 19296 KB Output is correct
5 Correct 18 ms 19296 KB Output is correct
6 Correct 22 ms 19336 KB Output is correct
7 Correct 24 ms 19340 KB Output is correct
8 Correct 30 ms 19340 KB Output is correct
9 Correct 20 ms 19340 KB Output is correct
10 Correct 25 ms 19508 KB Output is correct
11 Correct 21 ms 19508 KB Output is correct
12 Correct 20 ms 19508 KB Output is correct
13 Correct 22 ms 19508 KB Output is correct
14 Correct 19 ms 19508 KB Output is correct
15 Incorrect 19 ms 19508 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 36796 KB Output is correct
2 Correct 160 ms 36796 KB Output is correct
3 Correct 298 ms 37768 KB Output is correct
4 Correct 183 ms 37836 KB Output is correct
5 Correct 208 ms 37836 KB Output is correct
6 Correct 197 ms 38348 KB Output is correct
7 Correct 226 ms 38348 KB Output is correct
8 Correct 248 ms 38348 KB Output is correct
9 Correct 200 ms 38348 KB Output is correct
10 Correct 234 ms 38348 KB Output is correct
11 Correct 147 ms 38348 KB Output is correct
12 Correct 162 ms 38348 KB Output is correct
13 Correct 183 ms 38348 KB Output is correct
14 Correct 153 ms 38348 KB Output is correct
15 Correct 164 ms 38348 KB Output is correct
16 Correct 181 ms 38348 KB Output is correct
17 Correct 35 ms 38348 KB Output is correct
18 Correct 39 ms 38348 KB Output is correct
19 Correct 39 ms 38348 KB Output is correct
20 Correct 50 ms 38348 KB Output is correct
21 Correct 44 ms 38348 KB Output is correct
22 Correct 42 ms 38348 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 38348 KB Output is correct
2 Correct 23 ms 38348 KB Output is correct
3 Correct 23 ms 38348 KB Output is correct
4 Correct 19 ms 38348 KB Output is correct
5 Correct 21 ms 38348 KB Output is correct
6 Correct 21 ms 38348 KB Output is correct
7 Correct 23 ms 38348 KB Output is correct
8 Correct 25 ms 38348 KB Output is correct
9 Correct 36 ms 38348 KB Output is correct
10 Correct 22 ms 38348 KB Output is correct
11 Correct 22 ms 38348 KB Output is correct
12 Correct 21 ms 38348 KB Output is correct
13 Correct 25 ms 38348 KB Output is correct
14 Correct 24 ms 38348 KB Output is correct
15 Correct 21 ms 38348 KB Output is correct
16 Correct 23 ms 38348 KB Output is correct
17 Correct 24 ms 38348 KB Output is correct
18 Correct 20 ms 38348 KB Output is correct
19 Correct 19 ms 38348 KB Output is correct
20 Correct 23 ms 38348 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 38348 KB Output is correct
2 Correct 251 ms 38348 KB Output is correct
3 Correct 302 ms 38348 KB Output is correct
4 Correct 275 ms 38348 KB Output is correct
5 Correct 273 ms 38348 KB Output is correct
6 Correct 355 ms 48108 KB Output is correct
7 Correct 251 ms 48108 KB Output is correct
8 Correct 267 ms 48108 KB Output is correct
9 Correct 313 ms 48108 KB Output is correct
10 Correct 256 ms 48108 KB Output is correct
11 Correct 274 ms 48108 KB Output is correct
12 Correct 218 ms 48108 KB Output is correct
13 Correct 221 ms 48108 KB Output is correct
14 Correct 172 ms 48108 KB Output is correct
15 Correct 140 ms 48108 KB Output is correct
16 Correct 141 ms 48108 KB Output is correct
17 Correct 151 ms 48108 KB Output is correct
18 Correct 134 ms 48108 KB Output is correct
19 Correct 158 ms 48108 KB Output is correct
20 Correct 174 ms 48108 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 48108 KB Output is correct
2 Correct 22 ms 48108 KB Output is correct
3 Correct 23 ms 48108 KB Output is correct
4 Correct 21 ms 48108 KB Output is correct
5 Correct 25 ms 48108 KB Output is correct
6 Correct 37 ms 48108 KB Output is correct
7 Correct 21 ms 48108 KB Output is correct
8 Correct 30 ms 48108 KB Output is correct
9 Correct 20 ms 48108 KB Output is correct
10 Correct 20 ms 48108 KB Output is correct
11 Correct 22 ms 48108 KB Output is correct
12 Correct 23 ms 48108 KB Output is correct
13 Correct 20 ms 48108 KB Output is correct
14 Correct 24 ms 48108 KB Output is correct
15 Correct 22 ms 48108 KB Output is correct
16 Correct 22 ms 48108 KB Output is correct
17 Correct 25 ms 48108 KB Output is correct
18 Correct 21 ms 48108 KB Output is correct
19 Correct 24 ms 48108 KB Output is correct
20 Correct 19 ms 48108 KB Output is correct
21 Correct 19 ms 48108 KB Output is correct
22 Correct 19 ms 48108 KB Output is correct
23 Correct 21 ms 48108 KB Output is correct
24 Correct 19 ms 48108 KB Output is correct
25 Correct 18 ms 48108 KB Output is correct
26 Correct 21 ms 48108 KB Output is correct
27 Correct 21 ms 48108 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 48108 KB Output is correct
2 Correct 227 ms 48108 KB Output is correct
3 Correct 199 ms 48108 KB Output is correct
4 Correct 263 ms 48108 KB Output is correct
5 Correct 209 ms 48108 KB Output is correct
6 Correct 190 ms 48108 KB Output is correct
7 Correct 241 ms 48108 KB Output is correct
8 Correct 196 ms 48108 KB Output is correct
9 Correct 181 ms 48108 KB Output is correct
10 Correct 164 ms 48108 KB Output is correct
11 Correct 175 ms 48108 KB Output is correct
12 Correct 159 ms 48108 KB Output is correct
13 Correct 160 ms 48108 KB Output is correct
14 Correct 172 ms 48108 KB Output is correct
15 Correct 305 ms 48108 KB Output is correct
16 Correct 307 ms 48108 KB Output is correct
17 Correct 303 ms 48108 KB Output is correct
18 Correct 354 ms 48108 KB Output is correct
19 Correct 186 ms 48108 KB Output is correct
20 Correct 218 ms 48108 KB Output is correct
21 Correct 285 ms 48108 KB Output is correct
22 Correct 185 ms 48108 KB Output is correct
23 Correct 159 ms 48108 KB Output is correct
24 Correct 243 ms 48108 KB Output is correct
25 Correct 234 ms 48108 KB Output is correct
26 Correct 250 ms 48108 KB Output is correct
27 Correct 272 ms 48108 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19248 KB Output is correct
3 Correct 20 ms 19248 KB Output is correct
4 Correct 20 ms 19296 KB Output is correct
5 Correct 18 ms 19296 KB Output is correct
6 Correct 22 ms 19336 KB Output is correct
7 Correct 24 ms 19340 KB Output is correct
8 Correct 30 ms 19340 KB Output is correct
9 Correct 20 ms 19340 KB Output is correct
10 Correct 25 ms 19508 KB Output is correct
11 Correct 21 ms 19508 KB Output is correct
12 Correct 20 ms 19508 KB Output is correct
13 Correct 22 ms 19508 KB Output is correct
14 Correct 19 ms 19508 KB Output is correct
15 Incorrect 19 ms 19508 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19248 KB Output is correct
3 Correct 20 ms 19248 KB Output is correct
4 Correct 20 ms 19296 KB Output is correct
5 Correct 18 ms 19296 KB Output is correct
6 Correct 22 ms 19336 KB Output is correct
7 Correct 24 ms 19340 KB Output is correct
8 Correct 30 ms 19340 KB Output is correct
9 Correct 20 ms 19340 KB Output is correct
10 Correct 25 ms 19508 KB Output is correct
11 Correct 21 ms 19508 KB Output is correct
12 Correct 20 ms 19508 KB Output is correct
13 Correct 22 ms 19508 KB Output is correct
14 Correct 19 ms 19508 KB Output is correct
15 Incorrect 19 ms 19508 KB Output isn't correct
16 Halted 0 ms 0 KB -