Submission #677102

#	Time	Username	Problem	Language	Result	Execution time	Memory
677102		MohammadAghil	Amusement Park (JOI17_amusement_park)	C++17	70 / 100	41 ms	32852 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){
     if(k){
          vl[r] = k--;
          spe[r] = true;
     } else vl[r] = h[r]%lg;
     bt[r] = X>>vl[r]&1ll;
     vis[r] = true;
     par[r] = p;
     for(int c: adj[r]) if(!vis[c]){
          h[c] = h[r] + 1;
          dfs(c, k, r);
          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);
     vl[0] = 0, bt[0] = X&1ll;
     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];
ll ans;

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

int cnt;
void dfs2(int r, int p, bool cr){
     if(!cnt) return;
     cnt--;
     if(cr) ans |= 1ll<<vl[r];
     for(int c: adj2[r]) if(c - p) {
          dfs2(c, r, Move(c));
          if(!cnt) return;
          Move(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);
     vl[0] = 0;
     cnt = lg;
     if(spe[x]){
          dfs2(x, -1, cr);
     } else{
          while(par[x] + 1 && cnt){
               if(cr) ans |= 1ll<<vl[x];
               cr = Move(par[x]), x = par[x];
               cnt--;
          }
          if(cnt) cnt = lg, dfs2(0, -1, cr);
     }
     return ans;
}

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