Submission #296192

#	Time	Username	Problem	Language	Result	Execution time	Memory
296192		PedroBigMan	Star Trek (CEOI20_startrek)	C++14	50 / 100	280 ms	7136 KiB

startrek

#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;
      |                  ^

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15