oj.uz

Submission #64857

# Submission time Handle Problem Language Result Execution time Memory
64857 2018-08-06T00:04:25 Z qkxwsm Duathlon (APIO18_duathlon) C++17
66 / 100
 323 ms 67152 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);
                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

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 18 ms 19276 KB Output is correct
3 Correct 17 ms 19376 KB Output is correct
4 Correct 21 ms 19484 KB Output is correct
5 Correct 18 ms 19484 KB Output is correct
6 Correct 17 ms 19484 KB Output is correct
7 Correct 17 ms 19484 KB Output is correct
8 Correct 18 ms 19512 KB Output is correct
9 Correct 18 ms 19512 KB Output is correct
10 Correct 24 ms 19512 KB Output is correct
11 Correct 18 ms 19572 KB Output is correct
12 Correct 18 ms 19572 KB Output is correct
13 Correct 24 ms 19572 KB Output is correct
14 Correct 23 ms 19572 KB Output is correct
15 Incorrect 21 ms 19616 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 18 ms 19276 KB Output is correct
3 Correct 17 ms 19376 KB Output is correct
4 Correct 21 ms 19484 KB Output is correct
5 Correct 18 ms 19484 KB Output is correct
6 Correct 17 ms 19484 KB Output is correct
7 Correct 17 ms 19484 KB Output is correct
8 Correct 18 ms 19512 KB Output is correct
9 Correct 18 ms 19512 KB Output is correct
10 Correct 24 ms 19512 KB Output is correct
11 Correct 18 ms 19572 KB Output is correct
12 Correct 18 ms 19572 KB Output is correct
13 Correct 24 ms 19572 KB Output is correct
14 Correct 23 ms 19572 KB Output is correct
15 Incorrect 21 ms 19616 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 36736 KB Output is correct
2 Correct 214 ms 36892 KB Output is correct
3 Correct 275 ms 37812 KB Output is correct
4 Correct 277 ms 37948 KB Output is correct
5 Correct 247 ms 37948 KB Output is correct
6 Correct 301 ms 38440 KB Output is correct
7 Correct 239 ms 38440 KB Output is correct
8 Correct 240 ms 38440 KB Output is correct
9 Correct 191 ms 38440 KB Output is correct
10 Correct 214 ms 38440 KB Output is correct
11 Correct 171 ms 38440 KB Output is correct
12 Correct 198 ms 38440 KB Output is correct
13 Correct 110 ms 38440 KB Output is correct
14 Correct 115 ms 38440 KB Output is correct
15 Correct 172 ms 38440 KB Output is correct
16 Correct 92 ms 38440 KB Output is correct
17 Correct 30 ms 38440 KB Output is correct
18 Correct 31 ms 38440 KB Output is correct
19 Correct 38 ms 38440 KB Output is correct
20 Correct 31 ms 38440 KB Output is correct
21 Correct 33 ms 38440 KB Output is correct
22 Correct 28 ms 38440 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38440 KB Output is correct
2 Correct 22 ms 38440 KB Output is correct
3 Correct 24 ms 38440 KB Output is correct
4 Correct 47 ms 38440 KB Output is correct
5 Correct 19 ms 38440 KB Output is correct
6 Correct 19 ms 38440 KB Output is correct
7 Correct 22 ms 38440 KB Output is correct
8 Correct 22 ms 38440 KB Output is correct
9 Correct 25 ms 38440 KB Output is correct
10 Correct 26 ms 38440 KB Output is correct
11 Correct 19 ms 38440 KB Output is correct
12 Correct 30 ms 38440 KB Output is correct
13 Correct 23 ms 38440 KB Output is correct
14 Correct 22 ms 38440 KB Output is correct
15 Correct 19 ms 38440 KB Output is correct
16 Correct 19 ms 38440 KB Output is correct
17 Correct 18 ms 38440 KB Output is correct
18 Correct 23 ms 38440 KB Output is correct
19 Correct 19 ms 38440 KB Output is correct
20 Correct 19 ms 38440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 38440 KB Output is correct
2 Correct 292 ms 38440 KB Output is correct
3 Correct 242 ms 38440 KB Output is correct
4 Correct 198 ms 38440 KB Output is correct
5 Correct 211 ms 38440 KB Output is correct
6 Correct 287 ms 48228 KB Output is correct
7 Correct 278 ms 48228 KB Output is correct
8 Correct 259 ms 48228 KB Output is correct
9 Correct 323 ms 48228 KB Output is correct
10 Correct 232 ms 48228 KB Output is correct
11 Correct 247 ms 48228 KB Output is correct
12 Correct 279 ms 48228 KB Output is correct
13 Correct 238 ms 48228 KB Output is correct
14 Correct 168 ms 48228 KB Output is correct
15 Correct 131 ms 48228 KB Output is correct
16 Correct 118 ms 48228 KB Output is correct
17 Correct 151 ms 48228 KB Output is correct
18 Correct 127 ms 48228 KB Output is correct
19 Correct 137 ms 48228 KB Output is correct
20 Correct 193 ms 48228 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48228 KB Output is correct
2 Correct 20 ms 48228 KB Output is correct
3 Correct 21 ms 48228 KB Output is correct
4 Correct 20 ms 48228 KB Output is correct
5 Correct 19 ms 48228 KB Output is correct
6 Correct 31 ms 48228 KB Output is correct
7 Correct 23 ms 48228 KB Output is correct
8 Correct 24 ms 48228 KB Output is correct
9 Correct 23 ms 48228 KB Output is correct
10 Correct 22 ms 48228 KB Output is correct
11 Correct 23 ms 48228 KB Output is correct
12 Correct 26 ms 48228 KB Output is correct
13 Correct 23 ms 48228 KB Output is correct
14 Correct 23 ms 48228 KB Output is correct
15 Correct 25 ms 48228 KB Output is correct
16 Correct 66 ms 48228 KB Output is correct
17 Correct 21 ms 48228 KB Output is correct
18 Correct 22 ms 48228 KB Output is correct
19 Correct 19 ms 48228 KB Output is correct
20 Correct 23 ms 48228 KB Output is correct
21 Correct 20 ms 48228 KB Output is correct
22 Correct 23 ms 48228 KB Output is correct
23 Correct 22 ms 48228 KB Output is correct
24 Correct 21 ms 48228 KB Output is correct
25 Correct 21 ms 48228 KB Output is correct
26 Correct 23 ms 48228 KB Output is correct
27 Correct 19 ms 48228 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 48228 KB Output is correct
2 Correct 237 ms 48228 KB Output is correct
3 Correct 204 ms 48228 KB Output is correct
4 Correct 227 ms 48228 KB Output is correct
5 Correct 194 ms 48228 KB Output is correct
6 Correct 191 ms 48228 KB Output is correct
7 Correct 184 ms 48228 KB Output is correct
8 Correct 151 ms 48228 KB Output is correct
9 Correct 152 ms 48228 KB Output is correct
10 Correct 140 ms 48228 KB Output is correct
11 Correct 141 ms 48228 KB Output is correct
12 Correct 134 ms 48228 KB Output is correct
13 Correct 132 ms 48228 KB Output is correct
14 Correct 138 ms 48228 KB Output is correct
15 Correct 239 ms 57756 KB Output is correct
16 Correct 220 ms 57756 KB Output is correct
17 Correct 219 ms 59628 KB Output is correct
18 Correct 224 ms 59628 KB Output is correct
19 Correct 201 ms 59628 KB Output is correct
20 Correct 202 ms 59628 KB Output is correct
21 Correct 210 ms 59628 KB Output is correct
22 Correct 200 ms 59628 KB Output is correct
23 Correct 147 ms 59628 KB Output is correct
24 Correct 173 ms 63760 KB Output is correct
25 Correct 191 ms 65288 KB Output is correct
26 Correct 213 ms 65668 KB Output is correct
27 Correct 222 ms 67152 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 18 ms 19276 KB Output is correct
3 Correct 17 ms 19376 KB Output is correct
4 Correct 21 ms 19484 KB Output is correct
5 Correct 18 ms 19484 KB Output is correct
6 Correct 17 ms 19484 KB Output is correct
7 Correct 17 ms 19484 KB Output is correct
8 Correct 18 ms 19512 KB Output is correct
9 Correct 18 ms 19512 KB Output is correct
10 Correct 24 ms 19512 KB Output is correct
11 Correct 18 ms 19572 KB Output is correct
12 Correct 18 ms 19572 KB Output is correct
13 Correct 24 ms 19572 KB Output is correct
14 Correct 23 ms 19572 KB Output is correct
15 Incorrect 21 ms 19616 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 18 ms 19276 KB Output is correct
3 Correct 17 ms 19376 KB Output is correct
4 Correct 21 ms 19484 KB Output is correct
5 Correct 18 ms 19484 KB Output is correct
6 Correct 17 ms 19484 KB Output is correct
7 Correct 17 ms 19484 KB Output is correct
8 Correct 18 ms 19512 KB Output is correct
9 Correct 18 ms 19512 KB Output is correct
10 Correct 24 ms 19512 KB Output is correct
11 Correct 18 ms 19572 KB Output is correct
12 Correct 18 ms 19572 KB Output is correct
13 Correct 24 ms 19572 KB Output is correct
14 Correct 23 ms 19572 KB Output is correct
15 Incorrect 21 ms 19616 KB Output isn't correct
16 Halted 0 ms 0 KB -