oj.uz

Submission #946857

# Submission time Handle Problem Language Result Execution time Memory
946857 2024-03-15T06:41:11 Z shenfe1 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 33 ms 17212 KB 
#include "Joi.h"
 
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#pragma target("avx2")
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
 
const int MAX=1e5+15;
const int B=500;
const int maxB=1000;
const int N=104;
const int block=450;
const ll inf=1e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;
 
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
 
int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}
 
struct JOIKUN{
  vector<int> g[MAX];
  vector<int> g1[MAX];
  int use[MAX];
  int d[MAX],root;
 
  void dfs(int v){
    use[v]=1;
    for(auto to:g[v]){
      if(!use[to]){
        d[to]=d[v]+1;
        g1[v].pb(to);
        g1[to].pb(v);
        dfs(to);
      }
    }
  }
 
  int mxD=0;
  int D[MAX];
 
  void dfs1(int v,int p=-1){
    mxD=max(mxD,d[v]+1);
    for(auto to:g1[v]){
      if(to==p)continue;
      d[to]=d[v]+1;
      dfs1(to,v);
    }
  }
 
  void calc(int v,int p=-1){
    D[v]=v;
    for(auto to:g1[v]){
      if(to==p)continue;
      calc(to,v);
      if(d[D[v]]<d[D[to]])D[v]=D[to];
    }
  }
 
  int bit(ll i,int j){
    return (i>>j)&1;
  }
 
  vector<int> top;
 
  void topsort(int v,int p=-1){
    top.pb(v);
    for(auto to:g[v]){
      if(to==p)continue;
      topsort(to,v);
    }
  }
 
  void solve(int N,int M,int A[],int B[],ll X,int T){
    for(int i=0;i<M;i++){
      g[A[i]].pb(B[i]);
      g[B[i]].pb(A[i]);
    }
    dfs(0);
    for(int i=0;i<N;i++){
      use[i]=0;
      if(d[i]>d[root])root=i;
    }
    d[root]=0;
    dfs1(root);
    calc(root);
    if(mxD>=60){
      // cout<<X<<"\n";
      for(int i=0;i<N;i++){
        if(d[D[i]]+1>=60){
          MessageBoard(i,bit(X,d[i]%60));
          // cout<<d[i]<<" "<<bit(X,d[i]%60)<<"\n";
        }
        else{
          MessageBoard(i,0);
        }
      }
      return;
    }
    topsort(root);
    for(int i=0;i<N;i++){
      MessageBoard(top[i],bit(X,i%60));
    }
  }
}t;
 
void Joi(int N, int M, int A[], int B[], long long X, int T) {
  t.solve(N,M,A,B,X,T);
}
#include "Ioi.h"
 
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#pragma target("avx2")
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
 
const int MAX=1e5+15;
const int B=500;
const int maxB=1000;
const int N=104;
const int block=450;
const ll inf=1e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;
 
struct IOICHAN{
 
  ll ans=0;
 
  vector<int> g[MAX];
  vector<int> g1[MAX];
  int use[MAX];
  int d[MAX],root;
  int pr[MAX];
 
  void dfs(int v){
    use[v]=1;
    for(auto to:g[v]){
      if(!use[to]){
        d[to]=d[v]+1;
        g1[v].pb(to);
        g1[to].pb(v);
        dfs(to);
      }
    }
  }
 
  int mxD=0;
  int D[MAX];
  int big[MAX];
 
  void dfs1(int v,int p=-1){
    pr[v]=p;
    mxD=max(mxD,d[v]+1);
    for(auto to:g1[v]){
      if(to==p)continue;
      d[to]=d[v]+1;
      dfs1(to,v);
    }
  }
 
  void calc(int v,int p=-1){
    D[v]=v;
    big[v]=-1;
    for(auto to:g1[v]){
      if(to==p)continue;
      calc(to,v);
      if(d[D[v]]<d[D[to]]){
        D[v]=D[to];
        big[v]=to;
      }
    }
  }
 
  int bit(ll i,int j){
    return (i>>j)&1;
  }
 
  vector<int> top;
 
  void topsort(int v,int p=-1){
    top.pb(v);
    for(auto to:g[v]){
      if(to==p)continue;
      topsort(to,v);
    }
  }
 
  set<pii> st;
 
  ll solve(int N,int M,int A[],int B[],int P,int V,int T){
    for(int i=0;i<M;i++){
      g[A[i]].pb(B[i]);
      g[B[i]].pb(A[i]);
      st.in({A[i],B[i]});
      st.in({B[i],A[i]});
    }
    dfs(0);
    for(int i=0;i<N;i++){
      use[i]=0;
      if(d[i]>d[root])root=i;
    }
    d[root]=0;
    dfs1(root);
    calc(root);
    // cout<<mxD<<"\n";
    if(mxD+1>=60){
      // cout<<d[59]<<" "<<d[0]<<"\n";
      while(d[P]%60!=0||d[D[P]]-d[P]<59){
        V=Move(pr[P]);
        P=pr[P];
      }
      // cout<<P<<"\n";
      ans+=V*(1ll<<0);
      for(int i=1;i<60;i++){
        V=Move(big[P]);
        P=big[P];
        ans+=V*(1ll<<i);
      }
      return ans;
    }
    return -1;
    topsort(root);
    while(P!=root){
      V=Move(pr[P]);
      P=pr[P];
    }
    ans+=V*(1ll<<0);
    for(int i=1;i<60;i++){
      int L=top[i];
      while(P!=L){
        if(st.count({P,L})){
          V=Move(L);
          P=L;
        }
        else{
          V=Move(pr[P]);
          P=pr[P];
        }
      }
      ans+=V*(1ll<<i);
    }
    return ans;
  }
}g;
 
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
  return g.solve(N,M,A,B,P,V,T);
}

Compilation message

Joi.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("Ofast")
      | 
Joi.cpp:6: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    6 | #pragma target("avx2")
      | 

Ioi.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("Ofast")
      | 
Ioi.cpp:6: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    6 | #pragma target("avx2")
      |

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 11784 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16992 KB Output is correct
2 Correct 32 ms 16992 KB Output is correct
3 Correct 33 ms 16876 KB Output is correct
4 Incorrect 17 ms 14856 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11796 KB Output is correct
2 Correct 3 ms 11808 KB Output is correct
3 Correct 3 ms 11792 KB Output is correct
4 Correct 5 ms 12336 KB Output is correct
5 Correct 5 ms 12336 KB Output is correct
6 Correct 5 ms 12344 KB Output is correct
7 Correct 5 ms 12420 KB Output is correct
8 Correct 4 ms 12336 KB Output is correct
9 Correct 16 ms 15568 KB Output is correct
10 Correct 14 ms 15584 KB Output is correct
11 Correct 13 ms 15580 KB Output is correct
12 Correct 3 ms 11804 KB Output is correct
13 Correct 3 ms 11792 KB Output is correct
14 Correct 2 ms 11792 KB Output is correct
15 Correct 3 ms 11808 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16984 KB Output is correct
2 Correct 30 ms 16876 KB Output is correct
3 Correct 31 ms 16996 KB Output is correct
4 Incorrect 18 ms 15064 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16996 KB Output is correct
2 Correct 30 ms 16980 KB Output is correct
3 Correct 32 ms 17212 KB Output is correct
4 Incorrect 18 ms 15060 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -