Submission #344729

#	Time	Username	Problem	Language	Result	Execution time	Memory
344729		_zheksenov	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	1569 ms	22764 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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 N = 5e5 + 7;
const int INF = 1e9 + 7;

int n, m, k;
vector<int> g[N];
int max_distance = 0;
int answer = 0;
int par[N][2];
bool used[N];
int dist[N], dp[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 1; i <= n; i++) {
            memset(used, false, sizeof used);
            memset(dp, 0, sizeof dp);
            memset(par, 0, sizeof par);
            memset(dist, 0, sizeof dist);
            queue<int> q;
            q.push(i);
            used[i] = true;
            vector<int> order;
            while (!q.empty()) {
                auto u = q.front();
                q.pop();
                order.push_back(u);
                for (auto v : g[u]) {
                    if (!used[v]) {
                        par[v][0] = u;
                        used[v] = true;
                        q.push(v);
                        dist[v] = dist[u] + 1;
                    } else if (dist[v] == dist[u] + 1) {
                        par[v][1] = u;
                    }
                }
            }
            for (int i = 1; i <= n; i++) {
                if (chmax(max_distance, dist[i]))
                    answer = 0;
            }
            dp[i] = 1;
            for (auto u : order) { 
                for (auto v : g[u]) {
                    if (par[u][0] != v && par[u][1] != v)
                        continue;
                    dp[u] += dp[v];
                } 
                if (dist[u] == max_distance)
                    answer += dp[u];
            }
        }
        cout << answer / 2 << "\n";
        return 0;
    }
    return 0;
}

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