Submission #476312

#TimeUsernameProblemLanguageResultExecution timeMemory
476312MonkeyKingPapričice (COCI20_papricice)C++14
110 / 110
244 ms20264 KiB
//Original Code: //#include <self/utility> //#include <self/debug> //using namespace std; //int n; //vector<int> edges[200005]; //int sz[200005]; //int block[200005]; //vector<int> v1,v2; // //void calc(int x,int par,vector<int> &v) //{ // v.push_back(sz[x]); // for(auto u:edges[x]) // { // if(u==par) continue; // calc(u,x,v); // } //} // //pii go(int x,int par) //{ // pii o=mp(n-sz[x],x); // pii res=mp(inf,-1); // for(auto u:edges[x]) // { // if(u==par) continue; // chmax(o.first,sz[u]); // chmin(res,go(u,x)); // } // chmin(res,o); // return res; //} // //void dfs(int x,int par) //{ // sz[x]=1; // for(auto u:edges[x]) // { // if(u==par) continue; // dfs(u,x); // sz[x]+=sz[u]; // } //} // //int calc(int a,int b,int c) //{ // return max({a,b,c})-min({a,b,c}); //} // //int calc(const vector<int> &v1,const vector<int> &v2) //{ // int res=inf; // for(int x:v1) // { // int m=n-x; // int it=lower_bound(all(v2),m/2)-v2.begin(); // for(int i=max(it-5,0);i<min(it+5,(int)v2.size());i++) // { // chmin(res,calc(x,v2[i],m-v2[i])); // } // } // return res; //} // //vector<vector<int> > vv; //int main() //{ // freopen("input.txt","r",stdin); // cin>>n; // for(int i=0;i<n-1;i++) // { // int x,y; // scanf("%d%d",&x,&y); // x--; // y--; // edges[x].emplace_back(y); // edges[y].emplace_back(x); // } // dfs(0,-1); // int rt=go(0,-1).second; // dfs(rt,-1); // sort(all(edges[rt]),[](int x,int y){return sz[x]>sz[y];}); // for(auto u:edges[rt]) // { // vector<int> t; // calc(u,rt,t); // sort(all(t)); // vv.emplace_back(t); // } // int res=inf; // chmin(res,calc(vv[0],vv[1])); // int m=n-sz[edges[rt][0]]; // for(auto x:vv[0]) // { // if(x==sz[edges[rt][0]]) continue; // chmin(res,calc(m,x,m-x)); // } // cout<<res<<endl; // return 0; //} //substituted with C++ Inliner #ifndef _SELF_UTILITY #define _SELF_UTILITY 1 #include <numeric> #include <iostream> #include <algorithm> #include <cmath> #include <stdio.h> #include <stdlib.h> #include <vector> #include <map> #include <queue> #include <set> #include <string> #include <string.h> #include <stack> #include <assert.h> #include <bitset> #include <time.h> #define Endl endl #define mp make_pair #define mt make_tuple #define ll long long #define ull unsigned long long #define pii pair<int,int> #define over(A) {cout<<A<<endl;exit(0);} #define all(A) A.begin(),A.end() #define quickcin ios_base::sync_with_stdio(false); #ifdef __TAKE_MOD int mod; #else #ifdef __TAKE_CONST_MOD const int mod=__TAKE_CONST_MOD; #else const int mod=1000000007; #endif #endif const int gmod=3; const int inf=1039074182; #ifdef __TAKE_CONST_EPS const double eps=__TAKE_CONST_EPS; #else const double eps=1e-9; #endif const double pi=3.141592653589793238462643383279; const ll llinf=2LL*inf*inf; template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;} template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;} inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);} template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;} template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;} template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;} template <typename T> inline T mabs(T x) {return (x<0?-x:x);} using namespace std; #endif #ifndef _SELF_DEBUG #define _SELF_DEBUG 1 #ifndef _SELF_OPERATOR #define _SELF_OPERATOR 1 using namespace std; template <typename T> ostream & operator<<(ostream &cout, const vector<T> &vec) { cout << "{"; for (int i = 0; i < (int)vec.size(); i++) { cout << vec[i]; if (i != (int)vec.size() - 1) cout << ','; } cout << "}"; return cout; } template <typename T1, typename T2> ostream &operator<<(ostream &cout, pair<T1, T2> p) { cout << "(" << p.first << ',' << p.second << ")"; return cout; } template <typename T, typename T2> ostream &operator<<(ostream &cout, set<T, T2> s) { vector<T> t; for (auto x : s) t.push_back(x); cout << t; return cout; } template <typename T, typename T2> ostream &operator<<(ostream &cout, multiset<T, T2> s) { vector<T> t; for (auto x : s) t.push_back(x); cout << t; return cout; } template <typename T> ostream &operator<<(ostream &cout, queue<T> q) { vector<T> t; while (q.size()) { t.push_back(q.front()); q.pop(); } cout << t; return cout; } template <typename T1, typename T2, typename T3> ostream &operator<<(ostream &cout, map<T1, T2, T3> m) { for (auto &x : m) { cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl; } return cout; } template <typename T1, typename T2> void operator+=(pair<T1, T2> &x,const pair<T1, T2> y) { x.first += y.first; x.second += y.second; } template <typename T1,typename T2> pair<T1,T2> operator + (const pair<T1,T2> &x,const pair<T1,T2> &y) { return make_pair(x.first+y.first,x.second+y.second); } template <typename T1,typename T2> pair<T1,T2> operator - (const pair<T1,T2> &x,const pair<T1,T2> &y) { return mp(x.first-y.first,x.second-y.second); } template <typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> x) { return make_pair(-x.first, -x.second); } template <typename T> vector<vector<T>> operator~(vector<vector<T>> vec) { vector<vector<T>> v; int n = vec.size(), m = vec[0].size(); v.resize(m); for (int i = 0; i < m; i++) { v[i].resize(n); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { v[i][j] = vec[j][i]; } } return v; } #endif #include <sstream> void print0x(int x) { std::vector <int> vec; while(x) { vec.push_back(x&1); x>>=1; } std::reverse(vec.begin(),vec.end()); for(int i=0;i<(int)vec.size();i++) { std::cout<<vec[i]; } std::cout<<' '; } template <typename T> void print0x(T x,int len) { std::vector <int> vec; while(x) { std::cout<<(x&1); x>>=1; len--; // vec.push_back(x&1); // x>>=1; } while(len--) cout<<0; // reverse(vec.begin(),vec.end()); // for(int i=(int)vec.size();i<len;i++) // { // putchar('0'); // } // for(size_t i=0;i<vec.size();i++) // { // std::cout<<vec[i]; // } // std::cout<<' '; } vector<string> vec_splitter(string s) { s += ','; vector<string> res; while(!s.empty()) { res.push_back(s.substr(0, s.find(','))); s = s.substr(s.find(',') + 1); } return res; } void debug_out( vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx, __attribute__ ((unused)) int LINE_NUM) { cerr << endl; } template <typename Head, typename... Tail> void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") "; stringstream ss; ss << H; cerr << args[idx] << " = " << ss.str(); debug_out(args, idx + 1, LINE_NUM, T...); } #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__) #endif using namespace std; int n; vector<int> edges[200005]; int sz[200005]; int block[200005]; vector<int> v1,v2; void calc(int x,int par,vector<int> &v) { v.push_back(sz[x]); for(auto u:edges[x]) { if(u==par) continue; calc(u,x,v); } } pii go(int x,int par) { pii o=mp(n-sz[x],x); pii res=mp(inf,-1); for(auto u:edges[x]) { if(u==par) continue; chmax(o.first,sz[u]); chmin(res,go(u,x)); } chmin(res,o); return res; } void dfs(int x,int par) { sz[x]=1; for(auto u:edges[x]) { if(u==par) continue; dfs(u,x); sz[x]+=sz[u]; } } int calc(int a,int b,int c) { return max({a,b,c})-min({a,b,c}); } int calc(const vector<int> &v1,const vector<int> &v2) { int res=inf; for(int x:v1) { int m=n-x; int it=lower_bound(all(v2),m/2)-v2.begin(); for(int i=max(it-5,0);i<min(it+5,(int)v2.size());i++) { chmin(res,calc(x,v2[i],m-v2[i])); } } return res; } vector<vector<int> > vv; int main() { // freopen("input.txt","r",stdin); cin>>n; for(int i=0;i<n-1;i++) { int x,y; scanf("%d%d",&x,&y); x--; y--; edges[x].emplace_back(y); edges[y].emplace_back(x); } dfs(0,-1); int rt=go(0,-1).second; dfs(rt,-1); sort(all(edges[rt]),[](int x,int y){return sz[x]>sz[y];}); for(auto u:edges[rt]) { vector<int> t; calc(u,rt,t); sort(all(t)); vv.emplace_back(t); } int res=inf; chmin(res,calc(vv[0],vv[1])); int m=n-sz[edges[rt][0]]; for(auto x:vv[0]) { if(x==sz[edges[rt][0]]) continue; chmin(res,calc(m,x,m-x)); } cout<<res<<endl; return 0; }

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:404:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  404 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...