Submission #409521

#	Time	Username	Problem	Language	Result	Execution time	Memory
409521		amunduzbaev	Duathlon (APIO18_duathlon)	C++14	0 / 100	197 ms	33700 KiB

count_triplets

/* made by amunduzbaev */

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"

using namespace std;
//using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define tut(x) array<int, x> 
#define int long long

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//template<class T> using oset = tree<T, 
//null_type, less_equal<T>, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;

const int MAXN = 2e5+5;

class Articulation {
  public:
    std::vector<int> keyV, bcc[MAXN];
    int cnt;
    int gao(int n, const std::vector<int> e[]) {
      memset(tag, use = 0, sizeof(tag[0]) * n);
      memset(low, cnt = 0, sizeof(low[0]) * n);
      std::fill_n(bcc, n, keyV = std::vector<int>());
      for (int i = 0; i < n; ++i) if (!tag[i]) dfs(i, 1, e);
      return cnt;
    }
  private:
    int tag[MAXN], low[MAXN], dot[MAXN], use;
    void dfs(int x, int dep, const std::vector<int> e[]) {
      int src = 0, out = 1 < dep; dot[use++] = x;
      tag[x] = low[x] = dep;
      for (auto &y: e[x]) {
        if (!tag[y]) {
          dfs(y, dep + 1, e);
          low[x] = std::min(low[x], low[y]);
          if (low[y] >= tag[x]) {
            if (++out == 2) keyV.push_back(x);
            while (dot[--use] != y) bcc[dot[use]].push_back(cnt);
            bcc[x].push_back(cnt); bcc[y].push_back(cnt++);
          }
        } else if (tag[y] != tag[x] - 1 || src++) {
          low[x] = std::min(low[x], tag[y]);
        }
      }
    }
} bcc;

const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int used[N], sub[N];
vii edges[N];

void dfs(int u, int p = -1){
	used[u] = 1;
	sub[u] = (u < n);
	for(auto x : edges[u]){
		if(!used[x]) dfs(x, u), sub[u] += sub[x];
	}
} vii cmp;
void ddfs(int u, int p = -1){
	used[u] = 1;
	if(u >= n) cmp.pb(u);
	for(auto x : edges[u]) if(!used[x]) ddfs(x, u);
}

int take_3(int x){
	if(x < 3) return 0;
	return x * (x - 1) * (x - 2);
}

int take_2(int x){
	if(x < 2) return 0;
	return x * (x - 1);
}

/*

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
2 4

*/

void solve(int t_case){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b; cin>>a>>b, a--, b--;
		edges[a].pb(b), edges[b].pb(a);
	} m = bcc.gao(n, edges);
	for(int i=0;i<n;i++){
		edges[i].clear();
		for(auto x : bcc.bcc[i]) edges[i].pb(x + n), edges[x + n].pb(i);
	} vii tt;
	
	for(int i=0;i<n+m;i++){
		if(used[i]) continue;
		dfs(i), tt.pb(i), res += take_3(sub[i]);
	} memset(used, 0, sizeof used);
	
	for(auto rr : tt){
		cmp.clear(), ddfs(rr);
		for(auto x : cmp){
			int group = sz(edges[x]);
			for(auto ch : edges[x]){
				int T = 0;
				if(sub[ch] > sub[x]) T = sub[rr] - sub[ch];
				else T = sub[ch] - 1;
				res -= (group - 1) * take_2(T);
				if(group > 0 && T >= 1) res -= (group - 1) * T * 2;
				
				for(auto rs : edges[ch]){
					if(rs == x) continue;
					T -= (sz(edges[rs]) - 1);
				} res -= take_2(T);
			} 
		}
	} cout<<res<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void usaco(std::string)':
count_triplets.cpp:31:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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