oj.uz

Submission #340661

# Submission time Handle Problem Language Result Execution time Memory
340661 2020-12-28T05:44:19 Z tengiz05 Shymbulak (IZhO14_shymbulak) C++17
30 / 100
 1500 ms 1260 KB 
#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 5005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
vector<int> edges[N];
int max_distance = 0;
int answer = 0;
vector<int> par[N];
bool used[N];
int dist[N], dp[N];
void solve(int test_case){
	int i, j;
	cin >> n;
	for(i=0;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}
	for(int start=1;start<=n;start++){
		for(i=1;i<=n;i++){
			par[i].clear();
			used[i] = false;
			dist[i] = 0;
			dp[i] = 0;
		}
		queue<int> q;
		q.push(start);
		used[start] = true;
		vector<int> order;
		while(!q.empty()){
			auto u = q.front();q.pop();
			order.pb(u);
			for(auto v : edges[u]){
				if(!used[v]){
					par[v].pb(u);
					used[v] = true;
					q.push(v);
					dist[v] = dist[u] + 1;
				}else if(dist[v] == dist[u] + 1){
					par[v].pb(u);
				}
			}
		}
		for(i=1;i<=n;i++){
			if(chmax(max_distance, dist[i]))
				answer = 0;
		}
		dp[start] = 1;
		for(auto u : order){
			for(auto v : edges[u]){
				if(find(all(par[u]), v) == par[u].end())continue;
				dp[u] += dp[v];
			}if(dist[u] == max_distance)answer += dp[u];
		}
		//~ cout << "\n\n";
		//~ for(i=1;i<=n;i++)cout << dist[i] << ' ';cout << '\n';
		
		//~ for(i=1;i<=n;i++)cout << dp[i] << ' ';cout << '\n';
		//~ cout << "when start was " << start << " they were: " << max_distance << ' ' << answer << '\n';
		
	}
	assert(answer%2==0);
	cout << answer/2 << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

shymbulak.cpp: In function 'void solve(int)':
shymbulak.cpp:24:9: warning: unused variable 'j' [-Wunused-variable]
   24 |  int i, j;
      |         ^

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 748 KB Output is correct
2 Correct 26 ms 620 KB Output is correct
3 Correct 47 ms 620 KB Output is correct
4 Correct 54 ms 620 KB Output is correct
5 Correct 1448 ms 1132 KB Output is correct
6 Correct 1060 ms 1260 KB Output is correct
7 Execution timed out 1543 ms 1004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

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