oj.uz

Submission #946861

# Submission time Handle Problem Language Result Execution time Memory
946861 2024-03-15T06:46:38 Z shenfe1 Amusement Park (JOI17_amusement_park) C++17
63 / 100
 218 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=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];
      }
      ans+=V*(1ll<<0);
      for(int i=1;i<60;i++){
        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);
    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 3 ms 11800 KB Output is correct
2 Correct 2 ms 11804 KB Output is correct
3 Correct 3 ms 11808 KB Output is correct
4 Correct 3 ms 11804 KB Output is correct
5 Correct 3 ms 11788 KB Output is correct
6 Correct 4 ms 12056 KB Output is correct
7 Correct 4 ms 11812 KB Output is correct
8 Correct 3 ms 11808 KB Output is correct
9 Correct 3 ms 11808 KB Output is correct
10 Runtime error 218 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 28 ms 16952 KB Output is correct
2 Correct 30 ms 16924 KB Output is correct
3 Correct 31 ms 17048 KB Output is correct
4 Correct 19 ms 15076 KB Output is correct
5 Correct 17 ms 15576 KB Output is correct
6 Correct 18 ms 15068 KB Output is correct
7 Correct 18 ms 15328 KB Output is correct
8 Correct 19 ms 15044 KB Output is correct
9 Correct 23 ms 15068 KB Output is correct
10 Correct 17 ms 15076 KB Output is correct
11 Correct 17 ms 15056 KB Output is correct
12 Correct 17 ms 14796 KB Output is correct
13 Correct 17 ms 14780 KB Output is correct
14 Correct 17 ms 15052 KB Output is correct
15 Correct 18 ms 15064 KB Output is correct
16 Correct 19 ms 14940 KB Output is correct
17 Correct 19 ms 15072 KB Output is correct
18 Correct 22 ms 15416 KB Output is correct
19 Correct 18 ms 15072 KB Output is correct
20 Correct 13 ms 15064 KB Output is correct
21 Correct 13 ms 15068 KB Output is correct
22 Correct 17 ms 15064 KB Output is correct
23 Correct 19 ms 15064 KB Output is correct
24 Correct 18 ms 15312 KB Output is correct
25 Correct 17 ms 15072 KB Output is correct
26 Correct 17 ms 15316 KB Output is correct
27 Correct 18 ms 15064 KB Output is correct
28 Correct 17 ms 15068 KB Output is correct
29 Correct 17 ms 14804 KB Output is correct
30 Correct 17 ms 15052 KB Output is correct
31 Correct 4 ms 11792 KB Output is correct
32 Correct 3 ms 11800 KB Output is correct
33 Correct 3 ms 11812 KB Output is correct
34 Runtime error 198 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 2 ms 11812 KB Output is correct
2 Correct 2 ms 11804 KB Output is correct
3 Correct 4 ms 11804 KB Output is correct
4 Correct 4 ms 12340 KB Output is correct
5 Correct 5 ms 12336 KB Output is correct
6 Correct 5 ms 12340 KB Output is correct
7 Correct 5 ms 12336 KB Output is correct
8 Correct 5 ms 12340 KB Output is correct
9 Correct 14 ms 15576 KB Output is correct
10 Correct 14 ms 15580 KB Output is correct
11 Correct 13 ms 15580 KB Output is correct
12 Correct 4 ms 11788 KB Output is correct
13 Correct 3 ms 11804 KB Output is correct
14 Correct 3 ms 11788 KB Output is correct
15 Correct 3 ms 11788 KB Output is correct

Subtask #4
53.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16932 KB Output is correct
2 Correct 28 ms 16996 KB Output is correct
3 Correct 31 ms 16804 KB Output is correct
4 Partially correct 18 ms 15036 KB Partially correct
5 Correct 18 ms 15588 KB Output is correct
6 Correct 17 ms 15056 KB Output is correct
7 Correct 17 ms 15072 KB Output is correct
8 Correct 17 ms 15064 KB Output is correct
9 Correct 19 ms 15076 KB Output is correct
10 Correct 17 ms 15060 KB Output is correct
11 Correct 18 ms 15076 KB Output is correct
12 Correct 17 ms 14980 KB Output is correct
13 Partially correct 17 ms 14792 KB Partially correct
14 Partially correct 18 ms 15068 KB Partially correct
15 Partially correct 18 ms 15064 KB Partially correct
16 Partially correct 18 ms 15068 KB Partially correct
17 Correct 19 ms 15068 KB Output is correct
18 Partially correct 19 ms 15020 KB Partially correct
19 Partially correct 18 ms 15056 KB Partially correct
20 Correct 14 ms 15316 KB Output is correct
21 Correct 13 ms 15124 KB Output is correct
22 Correct 18 ms 15116 KB Output is correct
23 Correct 18 ms 15208 KB Output is correct
24 Correct 17 ms 15460 KB Output is correct
25 Correct 18 ms 15320 KB Output is correct
26 Correct 17 ms 15016 KB Output is correct
27 Correct 18 ms 15176 KB Output is correct
28 Correct 17 ms 15412 KB Output is correct
29 Correct 17 ms 14788 KB Output is correct
30 Correct 17 ms 15052 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16808 KB Output is correct
2 Correct 30 ms 16776 KB Output is correct
3 Correct 33 ms 16920 KB Output is correct
4 Incorrect 20 ms 15040 KB Output isn't correct
5 Halted 0 ms 0 KB -