oj.uz

Submission #108441

# Submission time Handle Problem Language Result Execution time Memory
108441 2019-04-29T15:22:35 Z PeppaPig Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 19856 KB 
#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;

int n, m;
int pre[N], low[N], ap[N], id[N];
vector<vector<int> > g(N), bcc;
vector<int> sz;

void tarjan(int u, int p) {
    static int idx = 0;
    static stack<int> S;
    pre[u] = low[u] = ++idx, S.emplace(u);
    int cnt = 0;
    for(int v : g[u]) if(v != p) {
        if(!pre[v]) {
            ++cnt;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if((!p && cnt > 1) || (p && low[v] >= pre[u])) ap[u] = 1;
            if(low[v] >= pre[u]) {
                bcc.emplace_back(vector<int>());
                bcc.back().emplace_back(u);
                while(bcc.back().back() != v) {
                    bcc.back().emplace_back(S.top());
                    S.pop();
                } 
            }
        } else low[u] = min(low[u], pre[v]);
    }
}

bitset<N> idart;

void gen_bct() {
    g.clear();
    g.emplace_back(vector<int>());
    sz.emplace_back(0);
    for(int i = 1; i <= n; i++) if(ap[i]) {
        idart[id[i] = g.size()] = true;
        g.emplace_back(vector<int>());
        sz.emplace_back(1);
    }
    for(vector<int> &cc : bcc) {
        g.emplace_back(vector<int>());
        sz.emplace_back(cc.size());
        for(int v : cc) {
            if(ap[v]) g[id[v]].emplace_back(g.size()-1), g[g.size()-1].emplace_back(id[v]);
            else id[v] = g.size()-1;
        }
    }
}

bitset<N> chk;
int siz[N];
long ans, sum_sz, sum_sz2;

int getsz(int u, int p) { siz[u] = 1; for(int v : g[u]) if(v != p && !chk[v]) siz[u] += getsz(v, u); return siz[u]; }

int find_cen(int u, int p, int all, pii &ret) {
    int mx = all - sz[u];
    for(int v : g[u]) if(v != p && !chk[v])
        mx = max(mx, find_cen(v, u, all, ret));
    ret = min(ret, pii(mx, u));
}

int noap_sz(int u) { return idart[u] ? 1 : sz[u] - g[u].size(); } //Non-overlap Size
int noad_sz(int u) { return sz[u] - 2 * (int)!idart[u]; } //Size with no 2 adjacent APs

void dfs(int u, int p, long all, bool fill) {
    if(!fill) ans += noap_sz(u) * (sum_sz2 + sum_sz * (all - idart[u])); //Start * (Change another subtree + Change this subtree)
    else {
        sum_sz += noap_sz(u); //Finish
        sum_sz2 += (all - idart[u]) * noap_sz(u); //Change and Finish
    }
    for(int v : g[u]) if(v != p && !chk[v]) dfs(v, u, all + noad_sz(v), fill);
}

void proc(int u) {
    getsz(u, u);
    pii ret(sz[u] + 1, -1);
    find_cen(u, u, sz[u], ret);
    chk[u = ret.y] = true;
    
    if(sz[u] > 2) ans += (sz[u] - 2) * (noap_sz(u) * (noap_sz(u)-1) / 2ll);
    sum_sz = noap_sz(u);
    sum_sz2 = idart[u] ? 0 : 1ll * noad_sz(u) * noap_sz(u);
    for(int v : g[u]) if(!chk[v]) {
        dfs(v, u, noad_sz(v), 0);
        dfs(v, u, noad_sz(v), 1);
    }
    for(int v : g[u]) if(!chk[v]) proc(v);
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b; i <= m; i++) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }
    for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, 0);
    gen_bct();

    for(int i = 1; i < (int)g.size(); i++) if(!chk[i]) proc(i);
    printf("%lld\n", 2ll * ans);

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int find_cen(int, int, int, std::pair<int, int>&)':
count_triplets.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2940 KB Output is correct
2 Correct 49 ms 2936 KB Output is correct
3 Correct 53 ms 2944 KB Output is correct
4 Incorrect 66 ms 2992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3064 KB Output is correct
2 Correct 58 ms 2936 KB Output is correct
3 Incorrect 19 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -