Submission #677131

#	Time	Username	Problem	Language	Result	Execution time	Memory
677131		MohammadAghil	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	37 ms	32884 KiB

Joi

      #include <bits/stdc++.h>
#include "Joi.h"
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e5 + 5, lg = 60, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

vector<int> adj[maxn], adj2[maxn];
int vl[maxn], par[maxn], h[maxn];
bool vis[maxn], bt[maxn], spe[maxn];
ll ans, X;

void dfs(int r, int& k, int p, int v = 0){
     if(k){
          vl[r] = lg - k;
          k--;
          spe[r] = true;
     } else vl[r] = v;
     bt[r] = X>>vl[r]&1ll;
     vis[r] = true;
     par[r] = p;
     for(int c: adj[r]) if(!vis[c]){
          dfs(c, k, r, k? 0: (v+lg-1)%lg);
          if(spe[r] && spe[c]){
               adj2[r].pb(c);
               adj2[c].pb(r);
          }
     }
}

void Joi(int n, int m, int a[], int b[], ll x, int T) { X = x;
     rep(i,0,m){
          adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
     }
     int tmp = lg;
     dfs(0, tmp, -1);
     rep(i,0,n) MessageBoard(i, bt[i]);
     return;
}

Ioi

      #include <bits/stdc++.h>
     #include "Ioi.h"
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 3e5 + 5, lg = 60, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

vector<int> adj[maxn], adj2[maxn];
int vl[maxn], par[maxn], h[maxn];
bool vis[maxn], spe[maxn], seen[maxn];
ll ans;

void dfs(int r, int& k, int p, int v = 0){
     if(k){
          vl[r] = lg - k;
          k--;
          spe[r] = true;
     } else vl[r] = v;
     vis[r] = true;
     par[r] = p;
     for(int c: adj[r]) if(!vis[c]){
          dfs(c, k, r, k? 0: (v+lg-1)%lg);
          if(spe[r] && spe[c]){
               adj2[r].pb(c);
               adj2[c].pb(r);
          }
     }
}

void dfs2(int r, bool cr){
     // er(r);
     vis[r] = true;
     if(cr) ans |= 1ll<<vl[r];
     seen[vl[r]] = true;
     for(int c: adj2[r]) if(c - par[r]){
          if(!seen[vl[c]]){
               // er(r, c);
               dfs2(c, Move(c));
               Move(r);
          }
     }
     if(par[r] + 1 && !vis[par[r]]){
          // er(r, par[r]);
          dfs2(par[r], Move(par[r]));
     }
}

ll Ioi(int n, int m, int a[], int b[], int x, int cr, int T) {
     rep(i,0,m){
          adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
     }
     int tmp = lg;
     dfs(0, tmp, -1);
     rep(i,0,n) vis[i] = false;
     int cnt = lg;
     while(!spe[x] && cnt){
          if(cr) ans |= 1ll<<vl[x];
          seen[vl[x]] = true;
          // er(vl[x], h[x]);
          cr = Move(par[x]), x = par[x];
          cnt--;
     }
     // er(x, f);
     if(cnt){
          dfs2(x, cr);
     }
     return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17