Submission #599425

#	Time	Username	Problem	Language	Result	Execution time	Memory
599425		Andyvanh1	Wells (CEOI21_wells)	C++14	0 / 100	0 ms	212 KiB

wells

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <stack>



using namespace std;

#define vt vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
#define MOD 1000000007

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef long double ld;
typedef vt<int> vi;
typedef pair<int,pair<int,int>> piii;

struct fwtree{
    vi arr;
    int sz;

    void init(int n){
        arr.resize(n+1);
        sz = n;
        FORR1(n+1)arr[i] = 0;
    }

    //remember difference between 0- and 1- indexing
    void add(int index, int val){
        while(index <= sz){
            arr[index]+=val;
            index+=index&-index;
        }
    }

    ll get(int index){
        ll val = 0;
        while(index!=0){
            val+=arr[index];
            index-=index&-index;
        }
        return val;
    }

    ll get(int l, int r){
        return get(r)-get(l-1);
    }

};

int N, O, M;
vi ceo;
ll fastexp(ll n, int m){
    if(m==0)return 1;
    ll cur = fastexp(n,m/2);
    cur = cur*cur;
    cur%=MOD;
    if(m&1){
        cur*=n;
        cur%=MOD;
    }
    return cur;
}

ll inv(ll x){
    return fastexp(x,MOD-2);
}



vt<vi> adjlist;
int degree[200005];
int dist[205][205];
int cur;

void dfs(int node, int par){
    for(auto& e: adjlist[node]){
        if(e!=par){
            dist[cur][e] = dist[cur][node]+1;
            dfs(e,node);
        }
    }
}


void solve(){
    int n,k;
    cin>>n>>k;
    adjlist.resize(n);
    FORR1(n-1){
        int u, v;
        cin>>u>>v;
        u--;v--;
        adjlist[u].pb(v);adjlist[v].pb(u);
    }
    FORR1(n){
        cur = i;
        dist[i][i] = 0;
        dfs(i,-1);
    }
    bool x = false;
    int ans = -1;
    FORR1(n){
        bool y = true;
        FORR2(j,n){
            FORR2(l,n){
                if(dist[j][l]==k-1){
                    int a = dist[i][j];
                    int b = dist[i][l];
                    int c = (a+b-k+1)>>1;
                    if((max(a,b)/k)*k<c){
                        y = false;
                        break;
                    }else{
                        if((min(a,b)/k)*k>=c){
                            y = false;
                            break;
                        }
                    }

                }
            }
            if(!y)break;
        }
        if(y){
            ans = i;
            x=true;
            break;
        }
    }
    cout<<(x ? "YES\n":"NO\n");
    cout<<ans;


    


}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

wells.cpp: In function 'void solve()':
wells.cpp:19:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
      |                             ^
wells.cpp:116:9: note: in expansion of macro 'FORR2'
  116 |         FORR2(j,n){
      |         ^~~~~
wells.cpp:19:29: warning: unnecessary parentheses in declaration of 'l' [-Wparentheses]
   19 | #define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++)
      |                             ^
wells.cpp:117:13: note: in expansion of macro 'FORR2'
  117 |             FORR2(l,n){
      |             ^~~~~

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