Submission #296192

#TimeUsernameProblemLanguageResultExecution timeMemory
296192PedroBigManStar Trek (CEOI20_startrek)C++14
50 / 100
280 ms7136 KiB
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=a; i<b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl #define INF 5000000000000000000LL ll mod=1000000007LL; template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} template<class A=ll> void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} class Matrix { public: ll a,b,c,d; Matrix() {a=1LL; b=0LL; c=0LL; d=1LL;} Matrix(ll x, ll y, ll w, ll z) {a=x; b=y; c=w; d=z;} Matrix operator *(Matrix X) { Matrix ANS(a*X.a+b*X.c,a*X.b+b*X.d,c*X.a+d*X.c,c*X.b+d*X.d); ANS.a%=mod; ANS.b%=mod; ANS.c%=mod; ANS.d%=mod; return ANS; } }; Matrix fastexp(Matrix A, ll e) { if(e==0LL) {Matrix id; return id;} if(e%2LL==0LL) {Matrix V = fastexp(A,e/2LL); return (V*V);} else {Matrix V=fastexp(A,e/2LL); return (V*V*A);} } class Tree { public: ll N; vector<ll> p; vector<vector<ll> > sons; vector<vector<ll> > adj; ll root; vector<bool> visited; vector<ll> sub; //number of nodes in subtree vector<ll> w,l,state; Tree(vector<vector<ll> > ad, ll r=0LL) { N=ad.size(); root=r; adj=ad; REP(i,0,N) {visited.pb(false);} vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); sub.pb(1LL);} DFS_Build(r,r); REP(i,0,N) {w.pb(-1); l.pb(-1); state.pb(-1);} } void Reset() { REP(i,0,N) {visited[i]=false;} } void DFS_Build(ll s, ll par) { p[s]=par; visited[s]=true; REP(i,0,adj[s].size()) { if(adj[s][i]==par) {continue;} sons[s].pb(adj[s][i]); DFS_Build(adj[s][i],s); sub[s]+=sub[adj[s][i]]; } return; } void fE(ll s) { ll c; REP(i,0,sons[s].size()) {c=sons[s][i]; fE(c);} if(sons[s].size()==0) {w[s]=1LL; l[s]=0LL; state[s]=0LL; return;} ll LC=0LL; ll lc=-1LL; state[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; if(state[c]==0LL) {LC++; lc=c;}} if(LC>0LL) {state[s]=1LL;} if(state[s]==0LL) { w[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; w[s]+=l[c];} w[s]++; l[s]=sub[s]-w[s]; } else if(LC>1LL) { w[s]=sub[s]; l[s]=0LL; } else { w[s]=sub[s]-sub[lc]+l[lc]; l[s]=sub[s]-w[s]; } } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll N,U; cin>>N>>U; vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);} pl cur; REP(i,0,N-1) { cin>>cur.ff>>cur.ss; cur.ff--; cur.ss--; adj[cur.ff].pb(cur.ss); adj[cur.ss].pb(cur.ff); } ll A,B,C,D,E,F,G; A=0LL; B=0LL; C=0LL; D=0LL; E=0LL; F=0LL; G=0LL; if(N<=1000LL) { REP(i,0,N) { Tree T(adj,i); T.fE(i); A+=T.w[i]; B+=T.l[i]; if(T.state[i]==1) {C++;} else {D++;} if(i==0) {E=A; F=B; G=C;} } A%=mod; B%=mod; Matrix M((C*N)%mod,A,(D*N)%mod,B); M=fastexp(M,U-1LL); pl las; las.ff=M.a*C+M.b*D; las.ss=M.c*C+M.d*D; las.ff%=mod; las.ss%=mod; ll ans=G*N*las.ff+E*las.ss; ans%=mod; if(ans<0) {ans+=mod;} cout<<ans<<endl; return 0LL; } return 0; }

Compilation message (stderr)

startrek.cpp: In member function 'void Tree::DFS_Build(ll, ll)':
startrek.cpp:20:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   90 |         REP(i,0,adj[s].size())
      |             ~~~~~~~~~~~~~~~~~    
startrek.cpp:90:9: note: in expansion of macro 'REP'
   90 |         REP(i,0,adj[s].size())
      |         ^~~
startrek.cpp: In member function 'void Tree::fE(ll)':
startrek.cpp:20:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  103 |         REP(i,0,sons[s].size()) {c=sons[s][i]; fE(c);}
      |             ~~~~~~~~~~~~~~~~~~   
startrek.cpp:103:9: note: in expansion of macro 'REP'
  103 |         REP(i,0,sons[s].size()) {c=sons[s][i]; fE(c);}
      |         ^~~
startrek.cpp:20:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  106 |         state[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; if(state[c]==0LL) {LC++; lc=c;}}
      |                           ~~~~~~~~~~~~~~~~~~
startrek.cpp:106:23: note: in expansion of macro 'REP'
  106 |         state[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; if(state[c]==0LL) {LC++; lc=c;}}
      |                       ^~~
startrek.cpp:20:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  110 |             w[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; w[s]+=l[c];}
      |                           ~~~~~~~~~~~~~~~~~~
startrek.cpp:110:23: note: in expansion of macro 'REP'
  110 |             w[s]=0LL; REP(i,0,sons[s].size()) {c=sons[s][i]; w[s]+=l[c];}
      |                       ^~~
startrek.cpp: In function 'int main()':
startrek.cpp:139:18: warning: variable 'F' set but not used [-Wunused-but-set-variable]
  139 |     ll A,B,C,D,E,F,G;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...