Submission #2113939
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define DBG cerr << '!' << endl; #define REP(i,n) for(ll (i) = (0);(i) < (n);++i) #define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i) #define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i)) #define PB push_back #define MP make_pair #define FI first #define SE second #define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;} #define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;} #define ALL(v) v.begin(),v.end() #define Decimal fixed<<setprecision(10) #define INF 1000000000 typedef long long ll; typedef pair<ll,ll> P; vector<vector<int> > v(2222); bool non[2222]; int dist[2222]; int n,k,ans = 2222; void bfs(int kyo,int a ,int b = -1) { REP(i,2222)dist[i] = INF; int ret = 0; queue<P> q; int endNode; q.push(P(a,b)); dist[a] = 0; if(b != -1) { q.push(P(b,a)); dist[b] = 0; } while(!q.empty()) { P p = q.front();q.pop(); int node = p.FI; REP(i,v[node].size()) { if(v[node][i] == p.SE)continue; endNode = v[node][i]; dist[endNode] = dist[node] + 1; if(dist[endNode] > kyo)ret++; q.push(P(endNode,node)); } } ans = min(ans,ret); } int main() { cin >> n >> k; vector<P> G; REP(i,n-1) { int a,b;cin >> a >> b; a--;b--; v[a].PB(b); v[b].PB(a); G.PB(P(a,b)); } if(k % 2 == 0) { REP(i,n)bfs(k/2,i); } else { REP(i,G.size())bfs(k/2,G[i].FI,G[i].SE); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Shorten Diameter |
User | seica |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1601 Byte |
Status | AC |
Exec Time | 80 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt |
All | 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 | AC | 1 ms | 256 KB |
001.txt | AC | 1 ms | 256 KB |
002.txt | AC | 1 ms | 256 KB |
003.txt | AC | 1 ms | 256 KB |
004.txt | AC | 1 ms | 256 KB |
005.txt | AC | 1 ms | 256 KB |
006.txt | AC | 1 ms | 256 KB |
007.txt | AC | 1 ms | 256 KB |
008.txt | AC | 1 ms | 256 KB |
009.txt | AC | 69 ms | 384 KB |
010.txt | AC | 51 ms | 384 KB |
011.txt | AC | 78 ms | 384 KB |
012.txt | AC | 68 ms | 384 KB |
013.txt | AC | 51 ms | 384 KB |
014.txt | AC | 77 ms | 384 KB |
015.txt | AC | 73 ms | 384 KB |
016.txt | AC | 54 ms | 384 KB |
017.txt | AC | 80 ms | 384 KB |
018.txt | AC | 3 ms | 384 KB |
019.txt | AC | 2 ms | 256 KB |
020.txt | AC | 19 ms | 384 KB |
021.txt | AC | 53 ms | 384 KB |
022.txt | AC | 13 ms | 384 KB |
023.txt | AC | 3 ms | 384 KB |
024.txt | AC | 10 ms | 384 KB |
025.txt | AC | 2 ms | 256 KB |
026.txt | AC | 63 ms | 384 KB |
027.txt | AC | 50 ms | 384 KB |
028.txt | AC | 50 ms | 384 KB |
029.txt | AC | 50 ms | 384 KB |
030.txt | AC | 41 ms | 384 KB |
031.txt | AC | 41 ms | 384 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |