Submission #71725

#	Time	Username	Problem	Language	Result	Execution time	Memory
71725		istlemin	Shymbulak (IZhO14_shymbulak)	C++14	30 / 100	1592 ms	263168 KiB

shymbulak

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

ll n;
vector<vi> e;

vi cycle;
vector<bool> seen;

vi nodes;

void findCycle(ll v,ll last){
    if(seen[v]){
		cycle.push_back(v);
        while(nodes.size()>0&&nodes[nodes.size()-1]!=v){
            cycle.push_back(nodes[nodes.size()-1]);
            nodes.pop_back();
        }
        return;
    }
    seen[v] = true;
    nodes.push_back(v);
    rep(i,0,e[v].size()){
		if(e[v][i]!=last) findCycle(e[v][i],v);
		if(cycle.size()>0) return;
    }
    nodes.pop_back();
}

pii getDepth(ll v,ll l1,ll l2){
	pii res = {0,1};
    rep(i,0,e[v].size()){
		if(e[v][i]==l1||e[v][i]==l2) continue;
		pii curr = getDepth(e[v][i],v,-1);
		curr.first++;
        if(curr.first>res.first){
			res = curr;
        } else if(curr.first==res.first){
            res.second += curr.second;
        }
	}
	return res;
}

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	e.resize(n);
	seen.resize(n);
    rep(i,0,n){
		ll a,b;
		cin>>a>>b;
		--a; --b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	vi allD;
	ll mxD = 0;

    rep(start,0,n){
        queue<pii> q;
        q.push({start,0});
        seen.assign(n,false);
        while(q.size()){
            ll v = q.front().first;
            ll d = q.front().second;
            q.pop();
            if(seen[v]) continue;
            seen[v] = true;
            allD.push_back(d);
            mxD = max(mxD,d);
            rep(i,0,e[v].size())
				if(!seen[e[v][i]])
					q.emplace(e[v][i],d+1);
        }
    }



    ll numMx = 0;
    rep(i,0,allD.size()) numMx += (allD[i]==mxD);
    numMx/=2;

	seen.assign(n,false);
	findCycle(0,-1);

    ll m = cycle.size();
    vector<pii> cycleDepth(m);
    rep(i,0,m){
		//cout<<cycle[i]<<" ";
        cycleDepth[i] = getDepth(cycle[i],cycle[(i+1)%m],cycle[(i+m-1)%m]);
    }
    //cout<<endl;


    if(m%2==0){
        rep(i,0,m/2){
            pii d1 = cycleDepth[i];
            pii d2 = cycleDepth[(i+m/2)%m];
            //cout<<cycle[i]<<" "<<cycle[(i+m/2)%m]<<": "<<endl;
            //cout<<d1.first<<" "<<d1.second<<" "<<d2.first<<" "<<d2.second<<endl;
            if(d1.first+d2.first+m/2==mxD){
                numMx += d1.second*d2.second;
            }
        }
    }

	cout<<numMx<<endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50