oj.uz

Submission #71725

# Submission time Handle Problem Language Result Execution time Memory
71725 2018-08-25T13:37:56 Z istlemin Shymbulak (IZhO14_shymbulak) C++14
30 / 100
 1500 ms 263168 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;

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 552 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 3 ms 580 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 3 ms 628 KB Output is correct
9 Correct 3 ms 628 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 3 ms 628 KB Output is correct
12 Correct 2 ms 628 KB Output is correct
13 Correct 4 ms 976 KB Output is correct
14 Correct 14 ms 2892 KB Output is correct
15 Correct 17 ms 2892 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4884 KB Output is correct
2 Correct 26 ms 9096 KB Output is correct
3 Correct 48 ms 9124 KB Output is correct
4 Correct 53 ms 9124 KB Output is correct
5 Runtime error 1191 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 263168 KB Time limit exceeded
2 Halted 0 ms 0 KB -