oj.uz

Submission #59953

# Submission time Handle Problem Language Result Execution time Memory
59953 2018-07-23T11:18:03 Z istlemin Duathlon (APIO18_duathlon) C++14
31 / 100
 740 ms 74200 KB 
#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-numChildren(treeE[v][i],v));
    }
    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Incorrect 3 ms 652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Incorrect 3 ms 652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 15772 KB Output is correct
2 Correct 173 ms 15804 KB Output is correct
3 Correct 480 ms 29604 KB Output is correct
4 Correct 352 ms 29604 KB Output is correct
5 Correct 369 ms 29604 KB Output is correct
6 Correct 442 ms 33312 KB Output is correct
7 Correct 466 ms 33312 KB Output is correct
8 Correct 458 ms 35036 KB Output is correct
9 Correct 436 ms 35036 KB Output is correct
10 Correct 391 ms 35036 KB Output is correct
11 Correct 267 ms 35036 KB Output is correct
12 Correct 309 ms 35036 KB Output is correct
13 Correct 257 ms 35036 KB Output is correct
14 Correct 301 ms 35036 KB Output is correct
15 Correct 248 ms 35804 KB Output is correct
16 Correct 230 ms 35868 KB Output is correct
17 Correct 35 ms 35868 KB Output is correct
18 Correct 39 ms 35868 KB Output is correct
19 Correct 32 ms 35868 KB Output is correct
20 Correct 42 ms 35868 KB Output is correct
21 Correct 31 ms 35868 KB Output is correct
22 Correct 32 ms 35868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35868 KB Output is correct
2 Correct 5 ms 35868 KB Output is correct
3 Correct 5 ms 35868 KB Output is correct
4 Correct 5 ms 35868 KB Output is correct
5 Correct 6 ms 35868 KB Output is correct
6 Correct 5 ms 35868 KB Output is correct
7 Correct 5 ms 35868 KB Output is correct
8 Correct 4 ms 35868 KB Output is correct
9 Correct 5 ms 35868 KB Output is correct
10 Correct 5 ms 35868 KB Output is correct
11 Correct 5 ms 35868 KB Output is correct
12 Correct 5 ms 35868 KB Output is correct
13 Correct 4 ms 35868 KB Output is correct
14 Correct 4 ms 35868 KB Output is correct
15 Correct 6 ms 35868 KB Output is correct
16 Correct 4 ms 35868 KB Output is correct
17 Correct 4 ms 35868 KB Output is correct
18 Correct 5 ms 35868 KB Output is correct
19 Correct 4 ms 35868 KB Output is correct
20 Correct 5 ms 35868 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 50188 KB Output is correct
2 Correct 597 ms 51592 KB Output is correct
3 Correct 646 ms 52740 KB Output is correct
4 Correct 606 ms 53952 KB Output is correct
5 Correct 594 ms 55024 KB Output is correct
6 Correct 672 ms 64460 KB Output is correct
7 Correct 740 ms 64460 KB Output is correct
8 Correct 603 ms 64460 KB Output is correct
9 Correct 580 ms 64460 KB Output is correct
10 Correct 575 ms 64460 KB Output is correct
11 Correct 593 ms 64460 KB Output is correct
12 Correct 521 ms 64460 KB Output is correct
13 Correct 562 ms 65080 KB Output is correct
14 Correct 543 ms 65080 KB Output is correct
15 Correct 412 ms 65080 KB Output is correct
16 Correct 267 ms 65080 KB Output is correct
17 Correct 545 ms 71272 KB Output is correct
18 Correct 501 ms 72140 KB Output is correct
19 Correct 423 ms 73700 KB Output is correct
20 Correct 442 ms 74200 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 74200 KB Output is correct
2 Correct 5 ms 74200 KB Output is correct
3 Incorrect 5 ms 74200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 74200 KB Output is correct
2 Correct 520 ms 74200 KB Output is correct
3 Incorrect 471 ms 74200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Incorrect 3 ms 652 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Incorrect 3 ms 652 KB Output isn't correct
8 Halted 0 ms 0 KB -