Submission #2999505


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


int count(int u, int prev, int r, vvi& next) {
    set<int> visited;
    visited.insert(prev);
#ifdef DEBUG
    fprintf(stderr, "count(u=%d, prev=%d,..., r=%d)", u,prev,r);
#endif

    queue<ii> q;
    q.push(ii(u,r));
    int cnt = 0;
    while (!q.empty()) {
        auto t = q.front(); q.pop();
        int u = t.first, rest = t.second;
        visited.insert(u);
        ++cnt;
        if (rest == 0) continue;
        for (int v: next[u]) {
            if (found(visited, v)) continue;
            q.push(ii(v,rest-1));
        }
    }
#ifdef DEBUG
    fprintf(stderr, " = %d\n", cnt);
#endif
    return cnt;
}

int solve(int N,int K,vi& a,vi& b) {
    vvi next(N);
    rep(i,N-1) {
        next[a[i]].pb(b[i]);
        next[b[i]].pb(a[i]);
    }

    int cmax = 0;
    if (K % 2) {
#ifdef DEBUG
        fprintf(stderr, "ODD; r=%d\n", K/2);
#endif
        rep(e,N-1) {
            int a0=a[e], b0=b[e];
#ifdef DEBUG
            fprintf(stderr, " e=%d-%d\n", a0, b0);
#endif
            int c = count(a0, b0, K/2, next) + count(b0, a0, K/2, next);
            cmax = max(cmax, c);
        }
    } else {
#ifdef DEBUG
        fprintf(stderr, "EVEN; r=%d\n", K/2);
#endif
        rep(u,N){
#ifdef DEBUG
            fprintf(stderr, " u=%d\n", u);
#endif
            int c = 1;
            for (int v: next[u]) {
#ifdef DEBUG
                fprintf(stderr, "  -> v=%d\n", v);
#endif
                c += count(v, u, K/2-1, next);
            }
            cmax = max(cmax, c);
        }
    }
    return N - cmax;
}

int main() {
    int N,K; cin >> N >> K;
    vi a(N-1),b(N-1);
    rep(i,N-1) {
        cin >> a[i] >> b[i];
        --a[i]; --b[i];
    }
    cout << solve(N,K,a,b) << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Shorten Diameter
User naoya_t
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3006 Byte
Status
Exec Time 735 ms
Memory 512 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 600 / 600 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
000.txt 1 ms 256 KB
001.txt 1 ms 256 KB
002.txt 1 ms 256 KB
003.txt 1 ms 256 KB
004.txt 1 ms 256 KB
005.txt 1 ms 256 KB
006.txt 1 ms 256 KB
007.txt 1 ms 256 KB
008.txt 1 ms 256 KB
009.txt 3 ms 384 KB
010.txt 4 ms 384 KB
011.txt 3 ms 384 KB
012.txt 609 ms 512 KB
013.txt 4 ms 384 KB
014.txt 5 ms 384 KB
015.txt 232 ms 384 KB
016.txt 15 ms 384 KB
017.txt 189 ms 512 KB
018.txt 15 ms 256 KB
019.txt 4 ms 256 KB
020.txt 157 ms 512 KB
021.txt 390 ms 384 KB
022.txt 5 ms 256 KB
023.txt 8 ms 256 KB
024.txt 44 ms 256 KB
025.txt 1 ms 256 KB
026.txt 348 ms 384 KB
027.txt 3 ms 384 KB
028.txt 735 ms 384 KB
029.txt 233 ms 384 KB
030.txt 4 ms 384 KB
031.txt 4 ms 384 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB