Submission #1134560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134560		KasymK	Shymbulak (IZhO14_shymbulak)	C++20	50 / 100	280 ms	776 KiB

shymbulak

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 5e3+5;
vector<int> adj[N];
int d[N], dp[N];

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int Mx=-1, answer=-1;
    for(int ad = 1; ad <= n; ++ad){
        memset(d, -1, sizeof d);
        memset(dp, 0, sizeof dp);
        queue<int> q;
        q.push(ad);
        d[ad]=0, dp[ad]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            tr(it, adj[x]){
                if(d[*it]==-1)
                    d[*it]=d[x]+1, dp[*it]=dp[x], q.push(*it);
                else if(d[*it]==d[x]+1)
                    dp[*it]+=dp[x];
            }
        }
        // for(int i = 1; i <= n; ++i)
        //     printf("%d = {%d => %d}\n", i, d[i], dp[i]);
        int mx=-1;
        for(int i = 1; i <= n; ++i)
            umax(mx, d[i]);
        if(umax(Mx, mx)){
            answer=0;
            for(int i = 1; i <= n; ++i)
                if(d[i]==mx)
                    answer+=dp[i];
            continue;
        }
        if(mx==Mx){
            for(int i = 1; i <= n; ++i)
                if(d[i]==mx)
                    answer+=dp[i];
        }
    }
    assert(~answer);
    // wr;
    printf("%d\n", answer/2);
    return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
shymbulak.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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