oj.uz

답안 #287325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287325 2020-08-31T15:33:39 Z wiwiho 철인 이종 경기 (APIO18_duathlon) C++14
0 / 100
 1000 ms 36752 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;

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

int n;

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

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 <= n; i++){
//        cerr << i << "  ";
//        printv(g[i], cerr);
//    }

    sz.resize(3 * n + 1, -1);
    cnt.resize(3 * n + 1);
    for(int i = n + 1; i < bcc; i++){
        for(int j : g[i]){
            if(!iscut[j]) cnt[i]++;
        }
    }

    for(int i = 1; i <= n; i++) if(iscut[i]) cnt[i] = 1;

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

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 36752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 640 KB Output is correct
2 Correct 36 ms 640 KB Output is correct
3 Correct 36 ms 640 KB Output is correct
4 Correct 37 ms 768 KB Output is correct
5 Correct 35 ms 760 KB Output is correct
6 Correct 36 ms 764 KB Output is correct
7 Correct 35 ms 768 KB Output is correct
8 Correct 36 ms 764 KB Output is correct
9 Correct 35 ms 640 KB Output is correct
10 Correct 36 ms 640 KB Output is correct
11 Correct 35 ms 672 KB Output is correct
12 Correct 35 ms 640 KB Output is correct
13 Correct 36 ms 760 KB Output is correct
14 Incorrect 36 ms 640 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1059 ms 28860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 640 KB Output is correct
2 Correct 35 ms 640 KB Output is correct
3 Incorrect 33 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 27604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -