Submission #409549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409549	2021-05-21T04:31:47 Z	rrrr10000	Mousetrap (CEOI17_mousetrap)	C++14	Compilation error	0 ms	0 KB

mousetrap

v#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,rt,st;cin>>n>>rt>>st;rt--;st--;
    if(rt==st)dame(0);
    vvi g(n);rep(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);g[b].pb(a);
    }
    vi dp(n);
    vi par(n);
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        par[i]=p;
        vi srt;
        for(ll x:g[i])if(x!=p){
            dfs(x,i);
            srt.pb(dp[x]);
        }rsort(srt);
        if(srt.size()>1)dp[i]=srt[1];
        dp[i]+=srt.size();
    };dfs(rt,-1);
    ll ok=n*2,ng=-1;
    // outv(dp);
    while(ok-ng>1){
        ll md=(ok+ng)/2;
        ll cnt=0;
        ll cur=st;
        vi num,al;
        while(cur!=rt){
            al.pb(cur);cur=par[cur];
        }reverse(all(al));
        for(ll x:al)num.pb(g[x].size()-2);num.back()++;
        vi rui=num;
        rep(i,rui.size()-1)rui[i+1]+=rui[i];
        bool able=true;
        for(int i=al.size()-1;i>=0;i--){
            ll tmp=0;vi srt;
            for(ll x:g[al[i]])if(x!=par[al[i]]&&(i==al.size()-1||x!=al[i+1])){
                if(cnt+rui[i]+dp[x]>md)tmp++;
            }
            cnt+=tmp;
            if(cnt>al.size()-i||cnt>md)able=false;
        }
        if(able)ok=md;
        else ng=md;
    }
    out(ok);
}

Compilation message

mousetrap.cpp:1:2: error: stray '#' in program
    1 | v#include <bits/stdc++.h>
      |  ^
mousetrap.cpp:1:1: error: 'v' does not name a type
    1 | v#include <bits/stdc++.h>
      | ^
mousetrap.cpp:19:9: error: 'pair' does not name a type; did you mean 'pi'?
   19 | typedef pair<ll,ll> P;
      |         ^~~~
      |         pi
mousetrap.cpp:20:9: error: 'tuple' does not name a type
   20 | typedef tuple<ll,ll,ll> PP;
      |         ^~~~~
mousetrap.cpp:21:9: error: 'tuple' does not name a type
   21 | typedef tuple<ll,ll,ll,ll> PPP;
      |         ^~~~~
mousetrap.cpp:22:10: error: 'vector' does not name a type
   22 | using vi=vector<ll>;
      |          ^~~~~~
mousetrap.cpp:23:11: error: 'vector' does not name a type
   23 | using vvi=vector<vi>;
      |           ^~~~~~
mousetrap.cpp:24:12: error: 'vector' does not name a type
   24 | using vvvi=vector<vvi>;
      |            ^~~~~~
mousetrap.cpp:25:13: error: 'vector' does not name a type
   25 | using vvvvi=vector<vvvi>;
      |             ^~~~~~
mousetrap.cpp:26:10: error: 'vector' does not name a type
   26 | using vp=vector<P>;
      |          ^~~~~~
mousetrap.cpp:27:11: error: 'vector' does not name a type
   27 | using vvp=vector<vp>;
      |           ^~~~~~
mousetrap.cpp:28:10: error: 'vector' does not name a type
   28 | using vb=vector<bool>;
      |          ^~~~~~
mousetrap.cpp:29:11: error: 'vector' does not name a type
   29 | using vvb=vector<vb>;
      |           ^~~~~~
mousetrap.cpp: In function 'void out(T)':
mousetrap.cpp:36:33: error: 'cout' was not declared in this scope; did you mean 'out'?
   36 | template<class T> void out(T a){cout<<a<<'\n';}
      |                                 ^~~~
      |                                 out
mousetrap.cpp: In function 'void outp(T)':
mousetrap.cpp:37:34: error: 'cout' was not declared in this scope; did you mean 'out'?
   37 | template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
      |                                  ^~~~
      |                                  out
mousetrap.cpp: In function 'void outvp(T)':
mousetrap.cpp:38:50: error: 'cout' was not declared in this scope; did you mean 'out'?
   38 | template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
      |                                                  ^~~~
      |                                                  out
mousetrap.cpp:38:88: error: 'cout' was not declared in this scope; did you mean 'out'?
   38 | template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
      |                                                                                        ^~~~
      |                                                                                        out
mousetrap.cpp: In function 'void outv(T)':
mousetrap.cpp:40:55: error: 'cout' was not declared in this scope; did you mean 'out'?
   40 | template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
      |                                                       ^~~~
      |                                                       out
mousetrap.cpp:40:65: error: 'cout' was not declared in this scope; did you mean 'out'?
   40 | template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
      |                                                                 ^~~~
      |                                                                 out
mousetrap.cpp:40:77: error: 'cout' was not declared in this scope; did you mean 'out'?
   40 | template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
      |                                                                             ^~~~
      |                                                                             out
mousetrap.cpp: In function 'void outset(T)':
mousetrap.cpp:46:93: error: 'cout' was not declared in this scope; did you mean 'out'?
   46 | template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
      |                                                                                             ^~~~
      |                                                                                             out
mousetrap.cpp:46:103: error: 'cout' was not declared in this scope; did you mean 'out'?
   46 | template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
      |                                                                                                       ^~~~
      |                                                                                                       out
mousetrap.cpp:46:121: error: 'cout' was not declared in this scope; did you mean 'out'?
   46 | template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
      |                                                                                                                         ^~~~
      |                                                                                                                         out
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:52:5: error: 'cin' was not declared in this scope
   52 |     cin.tie(0);ios::sync_with_stdio(false);
      |     ^~~
mousetrap.cpp:52:16: error: 'ios' has not been declared
   52 |     cin.tie(0);ios::sync_with_stdio(false);
      |                ^~~
mousetrap.cpp:55:5: error: 'vvi' was not declared in this scope
   55 |     vvi g(n);rep(i,n-1){
      |     ^~~
mousetrap.cpp:57:9: error: 'g' was not declared in this scope
   57 |         g[a].pb(b);g[b].pb(a);
      |         ^
mousetrap.cpp:59:5: error: 'vi' was not declared in this scope; did you mean 'fi'?
   59 |     vi dp(n);
      |     ^~
      |     fi
mousetrap.cpp:60:7: error: expected ';' before 'par'
   60 |     vi par(n);
      |       ^~~~
      |       ;
mousetrap.cpp:61:5: error: 'function' was not declared in this scope; did you mean 'union'?
   61 |     function<void(ll,ll)> dfs=[&](ll i,ll p){
      |     ^~~~~~~~
      |     union
mousetrap.cpp:61:24: error: expression list treated as compound expression in functional cast [-fpermissive]
   61 |     function<void(ll,ll)> dfs=[&](ll i,ll p){
      |                        ^
mousetrap.cpp:61:14: error: expected primary-expression before 'void'
   61 |     function<void(ll,ll)> dfs=[&](ll i,ll p){
      |              ^~~~
mousetrap.cpp:70:7: error: 'dfs' was not declared in this scope
   70 |     };dfs(rt,-1);
      |       ^~~
mousetrap.cpp:77:11: error: expected ';' before 'num'
   77 |         vi num,al;
      |           ^~~~
      |           ;
mousetrap.cpp:79:13: error: 'al' was not declared in this scope; did you mean 'll'?
   79 |             al.pb(cur);cur=par[cur];
      |             ^~
      |             ll
mousetrap.cpp:79:28: error: 'par' was not declared in this scope
   79 |             al.pb(cur);cur=par[cur];
      |                            ^~~
mousetrap.cpp:80:22: error: 'al' was not declared in this scope; did you mean 'll'?
   80 |         }reverse(all(al));
      |                      ^~
mousetrap.cpp:15:16: note: in definition of macro 'all'
   15 | #define all(a) a.begin(),a.end()
      |                ^
mousetrap.cpp:80:10: error: 'reverse' was not declared in this scope
   80 |         }reverse(all(al));
      |          ^~~~~~~
mousetrap.cpp:81:21: error: 'num' was not declared in this scope; did you mean 'enum'?
   81 |         for(ll x:al)num.pb(g[x].size()-2);num.back()++;
      |                     ^~~
      |                     enum
mousetrap.cpp:81:28: error: 'g' was not declared in this scope
   81 |         for(ll x:al)num.pb(g[x].size()-2);num.back()++;
      |                            ^
mousetrap.cpp:81:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   81 |         for(ll x:al)num.pb(g[x].size()-2);num.back()++;
      |         ^~~
mousetrap.cpp:81:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |         for(ll x:al)num.pb(g[x].size()-2);num.back()++;
      |                                           ^~~
mousetrap.cpp:81:43: error: 'num' was not declared in this scope; did you mean 'enum'?
   81 |         for(ll x:al)num.pb(g[x].size()-2);num.back()++;
      |                                           ^~~
      |                                           enum
mousetrap.cpp:82:11: error: expected ';' before 'rui'
   82 |         vi rui=num;
      |           ^~~~
      |           ;
mousetrap.cpp:83:15: error: 'rui' was not declared in this scope
   83 |         rep(i,rui.size()-1)rui[i+1]+=rui[i];
      |               ^~~
mousetrap.cpp:3:52: note: in definition of macro 'rep'
    3 | #define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
      |                                                    ^
mousetrap.cpp:86:24: error: expected ';' before 'srt'
   86 |             ll tmp=0;vi srt;
      |                        ^~~~
      |                        ;
mousetrap.cpp:87:22: error: 'g' was not declared in this scope
   87 |             for(ll x:g[al[i]])if(x!=par[al[i]]&&(i==al.size()-1||x!=al[i+1])){
      |                      ^
mousetrap.cpp:87:37: error: 'par' was not declared in this scope
   87 |             for(ll x:g[al[i]])if(x!=par[al[i]]&&(i==al.size()-1||x!=al[i+1])){
      |                                     ^~~
mousetrap.cpp:88:24: error: 'rui' was not declared in this scope
   88 |                 if(cnt+rui[i]+dp[x]>md)tmp++;
      |                        ^~~
mousetrap.cpp:88:31: error: 'dp' was not declared in this scope
   88 |                 if(cnt+rui[i]+dp[x]>md)tmp++;
      |                               ^~