Submission #59942

#	Time	Username	Problem	Language	Result	Execution time	Memory
59942		istlemin	Duathlon (APIO18_duathlon)	C++14	0 / 100	630 ms	41872 KiB

count_triplets

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

vi dfsNum;
vi dfsLow;
ll currDfsNum = 0;
vector<vi> e;

set<pii> bridges;


void dfs(ll v, ll l){
	if(dfsNum[v]!=-1) return;
    dfsNum[v] = dfsLow[v] = currDfsNum++;
    rep(i,0,e[v].size()){
		if(e[v][i]==l) continue;
        dfs(e[v][i],v);
        dfsLow[v] = min(dfsLow[v],dfsLow[e[v][i]]);
    }
}

vector<vi> cycles;
vi cycleIndices;
vector<bool> seen;

void getCycle(ll v){
	if(seen[v]) return;
	seen[v] = true;
	cycles[cycles.size()-1].push_back(v);
	cycleIndices[v] = cycles.size()-1;
    rep(i,0,e[v].size()){
        if(bridges.find({v,e[v][i]})==bridges.end())
			getCycle(e[v][i]);
    }
}

vector<vi> treeE;

vi dp;

ll numChildren(ll v,ll l){
	if(dp[v]!=-1) return dp[v];
	ll ans = cycles[v].size();
    rep(i,0,treeE[v].size()){
        if(treeE[v][i] == l) continue;
		ans += numChildren(treeE[v][i],v);
	}
	return dp[v] = ans;
}

ll getNum(ll v,ll l,ll childrenUp){
seen[v] = true;
    ll childSum = 0;
	vi childrenSizes;
    rep(i,0,treeE[v].size())
        if(treeE[v][i] != l){
			childSum += numChildren(treeE[v][i],v);
			childrenSizes.push_back(numChildren(treeE[v][i],v));
		}
	childSum+=childrenUp;
	childrenSizes.push_back(childrenUp);

	//cout<<v<<" "<<l<<" "<<childrenUp<<endl;

    ll ans = 0;
    ll sz = cycles[v].size();
	rep(i,0,childrenSizes.size()){
        ans += childrenSizes[i]*(childSum - childrenSizes[i])*sz;//c here
	//cout<<ans<<endl;
	}
	ans += childSum*(sz-1)*(sz-1)*2;//2 here
	//cout<<ans<<endl;
	ans += (sz)*(sz-1)*(sz-2);//3 here

	//cout<<ans<<endl;
    rep(i,0,treeE[v].size()){
        if(treeE[v][i] == l) continue;
        ans += getNum(treeE[v][i],v,childSum+sz-childrenSizes[i]);
    }
    return ans;

}

ll n,m;
ll brute(){
    ll ans = 0;
    set<ll> bridgeNodes;
    rep(i,0,n){
		bool bridgeNode = false;
		rep(j,0,e[i].size()){
            if(dfsNum[e[i][j]]>dfsNum[i]&&dfsLow[e[i][j]]>=dfsNum[i]){
				bridgeNode = true;
            }
		}
		if(bridgeNode||e[i].size()==1) {
			//cout<<i+1<<endl;
			bridgeNodes.insert(i);
		}
    }
    rep(s,0,n)
		rep(f,0,n){
			if(f==s)
				continue;
			bool fail = false;
			set<ll> neededNodes;
			vi p(n,-1);
			queue<pii> q;
			q.push({s,-2});
			while(q.size()){
				ll v = q.front().first;
				ll parent = q.front().second;
				q.pop();
				if(p[v]!=-1) continue;
				p[v] = parent;
				rep(i,0,e[v].size())
					q.push({e[v][i],v});
			}
			if(p[f]==-1) continue;
			ll v = f;
			neededNodes.insert(f);
			neededNodes.insert(s);
			while(p[v]!=-2){
				v = p[v];
				if(bridgeNodes.find(v)!=bridgeNodes.end()){
					neededNodes.insert(v);
				}
			}

            vector<bool> seen(n,false);
            queue<ll> q2;
            q2.push(s);
            while(q2.size()){
				ll v = q2.front();
				q2.pop();
				if(bridgeNodes.find(v)!=bridgeNodes.end()&&neededNodes.find(v)==neededNodes.end()) continue;
				if(seen[v]) continue;
				seen[v] = true;
                rep(i,0,e[v].size()) q2.push(e[v][i]);
            }
			ans -= 2;
            rep(i,0,n) ans += seen[i];

		}
	return ans;
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n>>m;
    e.resize(n);
    dfsNum.resize(n,-1);
    dfsLow.resize(n,-1);
    vector<pii> edges(m);
    rep(i,0,m){
        ll a,b;
        cin>>a>>b;
        --a; --b;
        edges[i] = {a,b};
        e[a].push_back(b);
        e[b].push_back(a);
    }

    rep(i,0,n)
		dfs(i,-1);

	//cout<<endl<<endl;

	rep(i,0,n){
		//cout<<i+1<<": "<<dfsNum[i]<<" "<<dfsLow[i]<<endl;
	}

    rep(i,0,m){
        ll a,b;
        tie(a,b) = edges[i];
        if(dfsNum[a]<dfsNum[b]&&dfsLow[b]==dfsNum[b]){
            bridges.insert({a,b});
            bridges.insert({b,a});
        }
        if(dfsNum[b]<dfsNum[a]&&dfsLow[a]==dfsNum[a]){
            bridges.insert({a,b});
            bridges.insert({b,a});
        }
    }
    //cout<<brute()<<endl;
    //return 0;

    cycleIndices.resize(n);
    seen.resize(n);
    rep(i,0,n){
		if(seen[i]) continue;
		cycles.push_back(vi(0));
		getCycle(i);
        //rep(j,0,cycles[cycles.size()-1].size()) cout<<cycles[cycles.size()-1][j]<<" ";
        //cout<<endl;
	}

	treeE.resize(cycles.size());

    trav(bridge,bridges){
        //cout<<bridge.first+1<<" "<<bridge.second+1<<endl;
        if(bridge.first<bridge.second){
			ll a = cycleIndices[bridge.first];
			ll b = cycleIndices[bridge.second];

            treeE[a].push_back(b);
            treeE[b].push_back(a);
        }
    }

    ll ans = 0;
	/*
    rep(i,0,cycles.size()){
		ll sz = cycles[i].size();
        ans += (sz)*(sz-1)*(sz-2);
    }*/

    dp.resize(cycles.size(),-1);

    seen.assign(cycles.size(),false);
    rep(i,0,cycles.size()){
        if(!seen[i]) {
			ans+=getNum(i,-1,0);

			//rep(j,0,cycles[i].size()) cout<<cycles[i][j]<<" ";
			//cout<<": "<<endl;

			//cout<<ans<<endl;
		}
    }

    cout<<ans<<endl;

}

Compilation message (stderr)

count_triplets.cpp: In function 'll getNum(ll, ll, ll)':
count_triplets.cpp:5:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i,a,b) for(int i = a; i<int(b);++i)
                    ^
count_triplets.cpp:65:5: note: in expansion of macro 'rep'
     rep(i,0,treeE[v].size())
     ^~~
count_triplets.cpp:70:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  childSum+=childrenUp;
  ^~~~~~~~
count_triplets.cpp: In function 'll brute()':
count_triplets.cpp:114:9: warning: unused variable 'fail' [-Wunused-variable]
    bool fail = false;
         ^~~~

• 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