oj.uz

Submission #59907

# Submission time Handle Problem Language Result Execution time Memory
59907 2018-07-23T09:48:28 Z istlemin Duathlon (APIO18_duathlon) C++14
0 / 100
 702 ms 40468 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;

vector<vi> dp;

ll getNum(ll v,ll l, ll toPlace){
	seen[v] = true;
	//cout<<v<<" "<<toPlace-1<<endl;
	if(dp[v][toPlace-1]!=-1) return dp[v][toPlace-1];
    ll ans = 0;
    ll sz = cycles[v].size();
	if(toPlace==1)
		ans += sz; //1 here
	if(toPlace==2)
		ans += (sz-1)*(sz-1);//2 here
	if(toPlace==3)
		ans += (sz)*(sz-1)*(sz-2); //3 here

    ll childSum = 0;
    rep(i,0,treeE[v].size())
        if(treeE[v][i] != l)
			childSum += getNum(treeE[v][i],v,1);

    rep(i,0,treeE[v].size()){
        if(treeE[v][i] == l) continue;
        if(toPlace==1)
			ans += getNum(treeE[v][i],v,1);//no here
        if(toPlace==2){
			ans += getNum(treeE[v][i],v,1)*sz;//1 here
			ans += getNum(treeE[v][i],v,2);//no here
		}
		if(toPlace==3){
			ll childNum = getNum(treeE[v][i],v,1);
			ans += (sz-1)*(sz-1)*childNum*2; //2 here
			ans += childNum*(childSum - childNum)*sz;//c here
			ans += getNum(treeE[v][i],v,2)*sz*2;//f or s here
			ans += getNum(treeE[v][i],v,3);//no here
		}
    }
    return dp[v][toPlace-1] = ans;
}

int main(){
	cin.sync_with_stdio(false);
    ll n,m;
    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});
        }
    }

    cycleIndices.resize(n);
    seen.resize(n);
    rep(i,0,n){
		if(seen[i]) continue;
		cycles.push_back(vi(0));
		getCycle(i);
	}

	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(),vi(3,-1));

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

    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Incorrect 3 ms 736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Incorrect 3 ms 736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 15964 KB Output is correct
2 Correct 212 ms 16044 KB Output is correct
3 Incorrect 497 ms 29696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 29696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 40468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 40468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 40468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Incorrect 3 ms 736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Incorrect 3 ms 736 KB Output isn't correct
8 Halted 0 ms 0 KB -