oj.uz

Submission #344665

# Submission time Handle Problem Language Result Execution time Memory
344665 2021-01-06T07:21:11 Z mansur Shymbulak (IZhO14_shymbulak) C++14
30 / 100
 322 ms 4972 KB 
#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define fix fixed<<setprecision
#define pii pair<int,int>
#define E exit (0)
#define int long long
const int inf=1e9;
int c[501][501],cnt;
vector<pii>adj[501];
map<int,bool>was;
void dfs(int u,int z,int mx,int t=0) {
	was[u]=1;
	if (t>mx) {
		was[u]=0;
		return;
	}
	if (u==z) {
		cnt++;
		was[u]=0;
		return;
	}
	for (auto e:adj[u]) {
		if (was[e.F]) {
			continue;
		}
		dfs(e.F,z,mx,t+1);
	}
	was[u]=0;
	return;
}
signed main() {
	//freopen("planting.in","r",stdin);
	//freopen("planting.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) {
	 	for (int j=1;j<=n;j++) {
	 		c[i][j]=inf;	
		}
	}
	for (int i=1;i<=n;i++) {
		c[i][i]=0;
		int a,b;
		cin>>a>>b;
		c[a][b]=c[b][a]=1;
		adj[a].pb({b,i});
		adj[b].pb({a,i});
	}
	for (int k=1;k<=n;k++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
			}	
		}
	}
	int mx=0;
	vector<pii>s;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (mx==c[i][j]) {
				s.pb({i,j});
			}
			if (mx<c[i][j]) {
				mx=c[i][j];
				s.clear();
				s.pb({i,j});
			}
		}
	}       
	int ans=0,i=0;
	for (auto e:s) {
		dfs(e.F,e.S,mx);
		ans+=cnt;
		for (int i=1;i<=500;i++) {
			was[i]=0;
        }
        cnt=0;
        i++;
	}
	cout<<ans/2;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 322 ms 1388 KB Output is correct
14 Correct 152 ms 2412 KB Output is correct
15 Correct 150 ms 2412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 4972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 4972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -