oj.uz

답안 #677077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677077 2023-01-02T08:39:48 Z MohammadAghil Amusement Park (JOI17_amusement_park) C++17
0 / 100
 40 ms 32860 KB 
      #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;
}
      #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, X;

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--;
          }
          dfs2(0, -1, cr);
     }
     return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28968 KB Output is correct
2 Incorrect 15 ms 28972 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 32784 KB Output is correct
2 Correct 37 ms 32776 KB Output is correct
3 Correct 37 ms 32732 KB Output is correct
4 Incorrect 27 ms 30700 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28960 KB Output is correct
2 Correct 15 ms 28968 KB Output is correct
3 Incorrect 16 ms 28976 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 32860 KB Output is correct
2 Correct 38 ms 32808 KB Output is correct
3 Correct 39 ms 32724 KB Output is correct
4 Incorrect 25 ms 30796 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 32836 KB Output is correct
2 Correct 40 ms 32692 KB Output is correct
3 Correct 38 ms 32752 KB Output is correct
4 Incorrect 28 ms 30788 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -