oj.uz

Submission #946876

# Submission time Handle Problem Language Result Execution time Memory
946876 2024-03-15T07:06:42 Z shenfe1 Amusement Park (JOI17_amusement_park) C++17
63 / 100
 213 ms 262144 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=1e6+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];
  bool use[MAX];
  int d[MAX],root=0;
  int cnt=0;
 
  void dfs(int v){
    use[v]=1;
    for(auto to:g[v]){
      if(!use[to]){
        cnt++;
        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);
    assert(cnt==N-1);
    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){
      for(int i=0;i<N;i++){
        MessageBoard(i,bit(X,d[i]%60));
      }
      return;
    }
    topsort(root);
    for(int i=0;i<sz(top);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=1e6+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;
 
  set<pii> st;
  vector<int> g[MAX];
  vector<int> g1[MAX];
  int use[MAX];
  int d[MAX],root=0;
  int pr[MAX];
  int cnt=0;
 
  void dfs(int v){
    use[v]=1;
    for(auto to:g[v]){
      if(!use[to]){
        d[to]=d[v]+1;
        cnt++;
        g1[v].pb(to);
        g1[to].pb(v);
        st.in({to,v});
        st.in({v,to});
        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;
      }
    }
  }
 
  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);
    }
  }
 
 
  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]);
    }
    dfs(0);
    assert(cnt==N-1);
    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){
      while(d[P]%60!=0||d[D[P]]-d[P]<59){
        V=Move(pr[P]);
        P=pr[P];
      }
      ans+=V*(1ll<<0);
      for(int i=1;i<60;i++){
        if(P==-1)assert(0);
        V=Move(big[P]);
        P=big[P];
        ans+=V*(1ll<<i);
      }
      return ans;
    }
    topsort(root);
    while(P!=root){
      V=Move(pr[P]);
      P=pr[P];
    }
    ans+=V*(1ll<<0);
    assert(sz(top)>=60);
    for(int i=1;i<60;i++){
      int L=top[i];
      int cnt=0;
      while(P!=L){
        cnt++;
        if(cnt>60){
          return -1;
        }
        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 Correct 22 ms 103700 KB Output is correct
2 Correct 23 ms 103780 KB Output is correct
3 Correct 23 ms 103748 KB Output is correct
4 Correct 23 ms 103708 KB Output is correct
5 Correct 22 ms 103704 KB Output is correct
6 Correct 23 ms 103724 KB Output is correct
7 Correct 22 ms 103700 KB Output is correct
8 Correct 24 ms 103748 KB Output is correct
9 Correct 25 ms 103740 KB Output is correct
10 Runtime error 196 ms 262144 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 107788 KB Output is correct
2 Correct 47 ms 107868 KB Output is correct
3 Correct 47 ms 107808 KB Output is correct
4 Correct 41 ms 107212 KB Output is correct
5 Correct 39 ms 107396 KB Output is correct
6 Correct 39 ms 107196 KB Output is correct
7 Correct 39 ms 107132 KB Output is correct
8 Correct 39 ms 107008 KB Output is correct
9 Correct 39 ms 107120 KB Output is correct
10 Correct 43 ms 107188 KB Output is correct
11 Correct 38 ms 107220 KB Output is correct
12 Correct 39 ms 106836 KB Output is correct
13 Correct 38 ms 106676 KB Output is correct
14 Correct 38 ms 106700 KB Output is correct
15 Correct 43 ms 106968 KB Output is correct
16 Correct 39 ms 106956 KB Output is correct
17 Correct 47 ms 106964 KB Output is correct
18 Correct 40 ms 106884 KB Output is correct
19 Correct 40 ms 106964 KB Output is correct
20 Correct 37 ms 107172 KB Output is correct
21 Correct 41 ms 107440 KB Output is correct
22 Correct 41 ms 107256 KB Output is correct
23 Correct 40 ms 107216 KB Output is correct
24 Correct 40 ms 107052 KB Output is correct
25 Correct 39 ms 107224 KB Output is correct
26 Correct 43 ms 107032 KB Output is correct
27 Correct 43 ms 107228 KB Output is correct
28 Correct 39 ms 107208 KB Output is correct
29 Correct 38 ms 106756 KB Output is correct
30 Correct 39 ms 106860 KB Output is correct
31 Correct 23 ms 103700 KB Output is correct
32 Correct 24 ms 103664 KB Output is correct
33 Correct 24 ms 103704 KB Output is correct
34 Runtime error 213 ms 262144 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 103688 KB Output is correct
2 Correct 23 ms 103740 KB Output is correct
3 Correct 24 ms 103720 KB Output is correct
4 Correct 25 ms 104272 KB Output is correct
5 Correct 25 ms 104244 KB Output is correct
6 Correct 27 ms 104236 KB Output is correct
7 Correct 24 ms 104240 KB Output is correct
8 Correct 25 ms 104248 KB Output is correct
9 Correct 38 ms 107332 KB Output is correct
10 Correct 34 ms 107524 KB Output is correct
11 Correct 35 ms 107476 KB Output is correct
12 Correct 23 ms 103736 KB Output is correct
13 Correct 24 ms 103608 KB Output is correct
14 Correct 25 ms 103700 KB Output is correct
15 Correct 26 ms 103692 KB Output is correct

Subtask #4
53.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 107792 KB Output is correct
2 Correct 55 ms 107652 KB Output is correct
3 Correct 47 ms 107780 KB Output is correct
4 Partially correct 45 ms 107136 KB Partially correct
5 Correct 39 ms 107412 KB Output is correct
6 Correct 45 ms 107144 KB Output is correct
7 Correct 40 ms 107188 KB Output is correct
8 Correct 40 ms 106948 KB Output is correct
9 Correct 39 ms 107136 KB Output is correct
10 Correct 40 ms 107260 KB Output is correct
11 Correct 39 ms 107212 KB Output is correct
12 Correct 41 ms 106644 KB Output is correct
13 Partially correct 46 ms 106664 KB Partially correct
14 Partially correct 38 ms 106724 KB Partially correct
15 Partially correct 41 ms 106964 KB Partially correct
16 Partially correct 41 ms 107100 KB Partially correct
17 Correct 41 ms 107168 KB Output is correct
18 Partially correct 41 ms 107152 KB Partially correct
19 Partially correct 40 ms 107012 KB Partially correct
20 Correct 39 ms 107008 KB Output is correct
21 Correct 37 ms 107108 KB Output is correct
22 Correct 46 ms 107184 KB Output is correct
23 Correct 46 ms 107220 KB Output is correct
24 Correct 45 ms 107256 KB Output is correct
25 Correct 43 ms 107204 KB Output is correct
26 Correct 44 ms 107164 KB Output is correct
27 Correct 40 ms 107208 KB Output is correct
28 Correct 41 ms 106976 KB Output is correct
29 Correct 38 ms 106704 KB Output is correct
30 Correct 38 ms 106888 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 107812 KB Output is correct
2 Correct 46 ms 107896 KB Output is correct
3 Correct 47 ms 107828 KB Output is correct
4 Incorrect 44 ms 107168 KB Output isn't correct
5 Halted 0 ms 0 KB -