제출 #132992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132992		12tqian	Duathlon (APIO18_duathlon)	C++14	0 / 100	1136 ms	1048580 KiB

count_triplets

#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>


using namespace std;


const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e5 + 5;
vi adj[MAX];
vi tree[MAX];
vi comp[MAX];
vi bcomp[MAX];
int sub[MAX];
int parent[MAX];
int dfs(int src, int par){
    parent[src] = par;
    sub[src] = sz(bcomp[src]);
    for(int nxt: tree[src]){
        if(nxt != par){
            sub[src] += dfs(nxt, src);
        }
    }
    sub[src] -= (sz(tree[src]) - (par==-1? 0: 1));///subtract out the the others, but include the parent
    return sub[src];
}
template<int SZ> struct BCC {
    int N;
    vi adj[SZ];
    vector<vpi> fin;

    void addEdge(int u, int v) { adj[u].pb(v), adj[v].pb(u); }

    int ti = 0, disc[SZ], low[SZ], comp[SZ], par[SZ];
    vpi st;

    void BCCutil(int u, bool root = 0) {
        disc[u] = low[u] = ti++;
        int child = 0;

        trav(i,adj[u]) if (i != par[u])
            if (disc[i] == -1) {
                child ++; par[i] = u;
                st.pb({u,i});
                BCCutil(i);
                low[u] = min(low[u],low[i]);

                // disc[u] < low[i]: bridge
                if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
                    vpi tmp;
                    while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
                    tmp.pb(st.back()), st.pop_back();
                    fin.pb(tmp);
                }
            } else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
                st.pb({u,i});
            }
    }

    void bcc(int _N) {
        N = _N;
        f1r(i,1,N+1) par[i] = disc[i] = low[i] = -1;
        f1r(i,1,N+1) if (disc[i] == -1) {
            BCCutil(i,1);
            if (sz(st)) fin.pb(st);
            st.clear();
        }
    }
};
BCC<MAX> bcc;
bool contains(int i, int x){
    int l = 0;
    int r = sz(bcomp[i]) - 1;
    while(l<= r){
        int m = (l+r)/2;
        if(bcomp[i][m] == x) return true;
        else if(bcomp[i][m]<x) l = m+1;
        else r = m-1;
    }
    return false;
}
int main(){
    fast_io();
    int n, m;
    cin >> n >> m;
    f0r(i, m){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].eb(v);
        adj[v].eb(u);
        bcc.addEdge(u+1, v+1);
    }
    bcc.bcc(n);
    int sz = sz(bcc.fin);
    f0r(i, sz){
       // cout << i <<" : ";
        for(auto e: bcc.fin[i]){
            comp[e.f-1].eb(i);
            comp[e.s-1].eb(i);
            bcomp[i].eb(e.f-1);
            bcomp[i].eb(e.s-1);
           // cout << "(" << e.f-1<< ", " << e.s-1<< ")" << " ";
        }
       // cout << endl;
    }
    f0r(i, n){
        set<int> s (all(comp[i]));
        comp[i].assign(all(s));
    }
    f0r(i, sz){
        set<int> s (all(bcomp[i]));
        bcomp[i].assign(all(s));
    }
    f0r(i,sz){
        for(int x: bcomp[i]){
            for(int nxt: comp[x]){
                if(nxt == i) continue;
                tree[i].eb(nxt);
            }
        }
    }

    dfs(0, -1);
    ll ans = 0;
    f0r(i, n){
        ll cur = n-1;
        cur = cur*(cur-1);
        for(int c: comp[i]){
            for(int nxt: tree[c]){
                if(contains(nxt, i)){
                    continue;
                }
                if(nxt == parent[c]){
                    ll subtract = n - sub[c] + 1;
                    //if(i == 0) cout << subtract<< " subtract " << sub[nxt] << " " << nxt << endl;
                    subtract *= (subtract - 1);
                    cur -= subtract;
                }
                else{
                    ll subtract = (sub[nxt]);
                    subtract *= (subtract-1);
                    cur -= subtract;
                }
            }
        }
     //   cout << i << " cur  " << cur << endl;
        ans += cur;
    }
    cout << ans << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
count_triplets.cpp: In member function 'void BCC<SZ>::BCCutil(int, bool)':
count_triplets.cpp:81:27: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
         trav(i,adj[u]) if (i != par[u])
                           ^
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10