oj.uz

Submission #289219

# Submission time Handle Problem Language Result Execution time Memory
289219 2020-09-02T13:14:34 Z wiwiho Duathlon (APIO18_duathlon) C++14
0 / 100
 184 ms 39416 KB 
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) (((a) + (b) - 1) / (b))
#define tomax(a, b) ((a) = max((a), (b)))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<vector<int>> tg, g;
int bcc;
vector<int> low, in;
int tts = 1;
stack<int> st;
vector<vector<int>> c;
vector<bool> iscut;

void dfsbcc(int now, int p){
    low[now] = in[now] = tts++;
    for(int i : tg[now]){
        if(i == p) continue;
        if(in[i]) low[now] = min(low[now], in[i]);
        else{
            dfsbcc(i, now);
            low[now] = min(low[now], low[i]);
            c[now].eb(i);
        }
        if(low[i] >= in[now] && now != 1) iscut[now] = true;
    }
    if(now == 1 && c[now].size() > 1) iscut[now] = true;
}

void dfsbcc2(int now, int p){
    st.push(now);
    for(int i : c[now]){
        dfsbcc2(i, now);
    }
    if(now == 1){
        if(st.size() > 1){
            while(!st.empty()){
                g[st.top()].eb(bcc);
                g[bcc].eb(st.top());
                st.pop();
            }
            bcc++;
        }
    }
    else if((p != 1 && low[now] >= in[p]) || (p == 1 && c[p].size() > 1)){
        while(!st.empty()){
            int t = st.top();
            g[st.top()].eb(bcc);
            g[bcc].eb(st.top());
            st.pop();
            if(t == now) break;
        }
        g[bcc].eb(p);
        g[p].eb(bcc);
        bcc++;
    }
}

vector<int> sz, cnt;

ll ans = 0;

int n;

void dfs1(int now, int p){
    sz[now] = now <= n;
    for(int i : g[now]){
        if(i == p) continue;
        dfs1(i, now);
        sz[now] += sz[i];
    }
}

void dfs2(int now, int p, int r){
    ll s = 0;
    for(int i : g[now]){
        if(i == p) continue;
        s += (ll) (sz[r] - sz[i]) * sz[i];
        if(now <= n && g[i].size() == 2) s-=2/*, cerr << now << "--\n"*/;
//        cerr << now << " " << i << " " << sz[r] - sz[i] << " " << sz[i] << "\n";
        dfs2(i, now, r);
    }
    s += (ll) (sz[r] - sz[now]) * sz[now];
    if(now <= n) s += sz[r] - 1/*, cerr << now << " " << sz[r] - 1 << "\n"*/;
    if(now <= n && now != p && g[p].size() == 2) s-=2/*, cerr << now << "--\n"*/;
    if(now > n && g[now].size() == 2) s-=2/*, cerr << now << "--\n"*/;
//    cerr << now << " r " << sz[now] << " " << sz[r] - sz[now] << "\n";
//    cerr << "test " << now << ' ' << s << "\n";
    ans += (ll) cnt[now] * s;
}

int main(){
    StarBurstStream

    int m;
    cin >> n >> m;
    tg.resize(n + 1);
    g.resize(3 * n + 1);
    bcc = n + 1;
    low.resize(n + 1);
    in.resize(n + 1);
    c.resize(n + 1);
    iscut.resize(n + 1);

    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        tg[u].eb(v);
        tg[v].eb(u);
    }

    for(int i = 1; i <= n; i++){
        if(in[i]) continue;
        dfsbcc(i, i);
        dfsbcc2(i, i);
    }

//    for(int i = 1; i < bcc; i++){
//        cerr << i << "  ";
//        printv(g[i], cerr);
//    }

    sz.resize(3 * n + 1, -MAX);
    cnt.resize(3 * n + 1);
    for(int i = n + 1; i < bcc; i++){
        cnt[i] = g[i].size();
    }

    for(int i = 1; i <= n; i++) cnt[i] = -1;
//    printv(cnt, cerr);

    for(int i = 1; i < bcc; i++){
        if(sz[i] != -MAX) continue;
        dfs1(i, i);
        dfs2(i, i, i);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 35696 KB Output is correct
2 Correct 144 ms 35696 KB Output is correct
3 Incorrect 156 ms 35448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 27672 KB Output is correct
2 Correct 148 ms 27772 KB Output is correct
3 Correct 143 ms 27640 KB Output is correct
4 Correct 148 ms 27640 KB Output is correct
5 Correct 149 ms 27640 KB Output is correct
6 Correct 171 ms 39416 KB Output is correct
7 Correct 176 ms 35040 KB Output is correct
8 Correct 178 ms 33368 KB Output is correct
9 Correct 177 ms 31352 KB Output is correct
10 Incorrect 150 ms 27696 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Incorrect 1 ms 640 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 27748 KB Output is correct
2 Correct 157 ms 27896 KB Output is correct
3 Correct 172 ms 27768 KB Output is correct
4 Correct 163 ms 27384 KB Output is correct
5 Correct 158 ms 27128 KB Output is correct
6 Correct 147 ms 26744 KB Output is correct
7 Correct 151 ms 26792 KB Output is correct
8 Correct 154 ms 26620 KB Output is correct
9 Correct 135 ms 26616 KB Output is correct
10 Correct 136 ms 26616 KB Output is correct
11 Correct 137 ms 26616 KB Output is correct
12 Correct 133 ms 26744 KB Output is correct
13 Correct 130 ms 26744 KB Output is correct
14 Correct 138 ms 28924 KB Output is correct
15 Correct 184 ms 35192 KB Output is correct
16 Correct 183 ms 32632 KB Output is correct
17 Correct 174 ms 33784 KB Output is correct
18 Correct 183 ms 31608 KB Output is correct
19 Incorrect 159 ms 27384 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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