제출 #133524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133524		12tqian	철인 이종 경기 (APIO18_duathlon)	C++14	90 / 100	1079 ms	94308 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>

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;


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 comp[MAX];
vi bcomp[MAX];
ll precomp[MAX];
int get_sz[MAX];
int bad[MAX];
unordered_map<int, int> vis;
unordered_map<int, int> sub;
unordered_map<int, int> parent;
unordered_map<int, vi> tree1;
vi cutpoints[MAX];
template<int SZ> struct DSU{
    int par[SZ], sz[SZ];
    DSU(){
        for(int i = 0; i<SZ; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    inline int get(int x){
        if(par[x] != x){
            par[x] = get(par[x]);
        }
        return par[x];
    }
    inline bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(x == y){
            return false;
        }
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
};
DSU<MAX> d;
inline int dfs(int src, int par){
//    assert(times<=1e6);
    vis[src] = 1;
    parent[src] = par;
    sub[src] = sz(bcomp[src]);
    if(src>=MAX){
        sub[src] = sz(bcomp[src - MAX]) - bad[src-MAX];
    }
    else{
        sub[src] = 1;
    }
    for(int nxt: tree1[src]){
        if(nxt != par){
            sub[src] += dfs(nxt, src);
        }
    }
    return sub[src];
}
template<int SZ> struct BCC {
    int N;
    vi adj[SZ];
    vector<vpi> fin;

    inline 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;

    inline 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;
int n;
inline int get(int above, int below){
    if(parent[below] == above){
        return sub[below];
    }
    else{
        return get_sz[below] - sub[above];
    }
}
int main(){
    //auto start = chrono::high_resolution_clock::now();
  //  io("test");
    fast_io();
    int m;
    //cin >> n >> m;
    scanf("%d %d", &n, &m);
    f0r(i, m){
        int u, v;
        scanf("%d %d", &u, &v);
      //  cin >> u >> v;
        u--;
        v--;
        d.unite(u, v);
        adj[u].eb(v);
        adj[v].eb(u);
        bcc.addEdge(u+1, v+1);
    }
    f0r(i, n){
        get_sz[i] = d.sz[d.get(i)];
    }
    bcc.bcc(n);
    int sz = sz(bcc.fin);
    f0r(i, sz){
        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);
        }
    }

    f0r(i, n){
       // set<int> s (all(comp[i]));
       // comp[i].assign(all(s));
        sort(all(comp[i]));
        comp[i].erase(unique(all(comp[i])), comp[i].end());
        for(auto x: comp[i]){
            bcomp[x].eb(i);
        }
    }
   /* f0r(i, sz){
        set<int> s (all(bcomp[i]));
        bcomp[i].assign(all(s));
    }*/

    f0r(i, n){
        if(sz(comp[i]) == 1)continue;
        for(int c: comp[i]){
            tree1[i].eb(c+MAX);
            tree1[c+MAX].eb(i);
        }
    }
    f0r(i,sz){
        for(int x: bcomp[i]){
            if(sz(comp[x]) >1){
                bad[i]++;
                cutpoints[i].eb(x);
            }
        }
    }
    //dfs(MAX, -1);
    /*auto end1 = chrono::high_resolution_clock::now();

    // Calculating total time taken by the program.
    double time_taken1 =
      chrono::duration_cast<chrono::nanoseconds>(end1 - start).count();

    time_taken1 *= 1e-9;

    cout << "Time taken by program is : " << fixed
         << time_taken1 << setprecision(9);
    cout << " sec" << endl;*/
    f0r(i, sz){
        if(vis.find(i + MAX) == vis.end()){
            dfs(i+MAX, -1);
        }
    }

    f0r(i, sz){
        for(int x: cutpoints[i]){
            ll val = get(i+MAX, x);
            precomp[i] += (val)*(val-1);
        }
    }

    ll ans = 0;
    f0r(i, n){
        ll cur = get_sz[i] - 1;
        if(sz(comp[i]) == 1){
            ///not a cut point
            cur *=(cur-1);
            int c = comp[i][0];
            for(int pnt: cutpoints[c]){
        //    for(auto pnt: bcomp[c]){
                //if(sz(comp[pnt]) > 1){///cut point
                    ll val = get(c+MAX, pnt);
                    cur -= val*(val-1);
               // }
            }
            ans += cur;
        }
        else{
            cur *= (cur-1);
            for(int nxt: tree1[i]){
                ll val = precomp[nxt-MAX];
                ll subtract = get(nxt, i);
                val -= subtract*(subtract - 1);
                cur -= val;
            }
            ans += cur;
        }
        //cout << i << " " << cur << endl;
    }
    cout << ans << endl;
  /* // cout << parent[1]- MAX << endl;
    //cout << sub[3+MAX] << endl;
   // cout << sub[5]<< endl;
    auto end = chrono::high_resolution_clock::now();

    // Calculating total time taken by the program.
    double time_taken =
      chrono::duration_cast<chrono::nanoseconds>(end - start).count();

    time_taken *= 1e-9;

    cout << "Time taken by program is : " << fixed
         << time_taken << setprecision(9);
    cout << " sec" << endl;*/
    return 0;
}

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

count_triplets.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:47:17: warning: unused variable 'FOUT' [-Wunused-variable]
     const char* FOUT = fout.c_str();
                 ^~~~
count_triplets.cpp: In member function 'void BCC<SZ>::BCCutil(int, bool)':
count_triplets.cpp:125: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:48: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: In function 'int main()':
count_triplets.cpp:170: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:173:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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