oj.uz

Submission #946856

# Submission time Handle Problem Language Result Execution time Memory
946856 2024-03-15T06:38:48 Z shenfe1 Amusement Park (JOI17_amusement_park) C++17
63 / 100
 201 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];
      }
      // 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;
    }
    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 Correct 3 ms 11804 KB Output is correct
2 Correct 2 ms 11792 KB Output is correct
3 Correct 3 ms 11804 KB Output is correct
4 Correct 3 ms 11804 KB Output is correct
5 Correct 2 ms 11808 KB Output is correct
6 Correct 2 ms 11808 KB Output is correct
7 Correct 3 ms 11812 KB Output is correct
8 Correct 4 ms 12400 KB Output is correct
9 Correct 2 ms 11808 KB Output is correct
10 Runtime error 201 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 37 ms 16924 KB Output is correct
2 Correct 31 ms 17288 KB Output is correct
3 Correct 32 ms 17400 KB Output is correct
4 Correct 19 ms 15416 KB Output is correct
5 Correct 19 ms 15668 KB Output is correct
6 Correct 19 ms 15428 KB Output is correct
7 Correct 20 ms 15416 KB Output is correct
8 Correct 18 ms 15424 KB Output is correct
9 Correct 19 ms 15420 KB Output is correct
10 Correct 16 ms 15428 KB Output is correct
11 Correct 18 ms 15428 KB Output is correct
12 Correct 16 ms 14880 KB Output is correct
13 Correct 17 ms 14884 KB Output is correct
14 Correct 17 ms 15148 KB Output is correct
15 Correct 18 ms 15424 KB Output is correct
16 Correct 18 ms 15408 KB Output is correct
17 Correct 19 ms 15416 KB Output is correct
18 Correct 19 ms 15404 KB Output is correct
19 Correct 24 ms 15352 KB Output is correct
20 Correct 14 ms 15416 KB Output is correct
21 Correct 14 ms 15428 KB Output is correct
22 Correct 18 ms 15428 KB Output is correct
23 Correct 17 ms 15528 KB Output is correct
24 Correct 19 ms 15408 KB Output is correct
25 Correct 18 ms 15420 KB Output is correct
26 Correct 18 ms 15408 KB Output is correct
27 Correct 18 ms 15416 KB Output is correct
28 Correct 18 ms 15416 KB Output is correct
29 Correct 17 ms 14880 KB Output is correct
30 Correct 17 ms 15404 KB Output is correct
31 Correct 4 ms 11804 KB Output is correct
32 Correct 3 ms 11796 KB Output is correct
33 Correct 2 ms 12216 KB Output is correct
34 Runtime error 189 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 11788 KB Output is correct
2 Correct 2 ms 11792 KB Output is correct
3 Correct 3 ms 11792 KB Output is correct
4 Correct 4 ms 12284 KB Output is correct
5 Correct 5 ms 12360 KB Output is correct
6 Correct 4 ms 12352 KB Output is correct
7 Correct 6 ms 12616 KB Output is correct
8 Correct 5 ms 12568 KB Output is correct
9 Correct 17 ms 15920 KB Output is correct
10 Correct 14 ms 15932 KB Output is correct
11 Correct 13 ms 15928 KB Output is correct
12 Correct 4 ms 11796 KB Output is correct
13 Correct 3 ms 11808 KB Output is correct
14 Correct 3 ms 11796 KB Output is correct
15 Correct 3 ms 11808 KB Output is correct

Subtask #4
53.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16984 KB Output is correct
2 Correct 31 ms 17500 KB Output is correct
3 Correct 32 ms 17240 KB Output is correct
4 Partially correct 19 ms 15408 KB Partially correct
5 Correct 18 ms 15940 KB Output is correct
6 Correct 19 ms 15416 KB Output is correct
7 Correct 18 ms 15416 KB Output is correct
8 Correct 19 ms 15688 KB Output is correct
9 Correct 22 ms 15408 KB Output is correct
10 Correct 17 ms 15420 KB Output is correct
11 Correct 17 ms 15412 KB Output is correct
12 Correct 17 ms 14892 KB Output is correct
13 Partially correct 19 ms 14884 KB Partially correct
14 Partially correct 18 ms 15292 KB Partially correct
15 Partially correct 19 ms 15312 KB Partially correct
16 Partially correct 19 ms 15408 KB Partially correct
17 Correct 20 ms 15396 KB Output is correct
18 Partially correct 19 ms 15400 KB Partially correct
19 Partially correct 20 ms 15416 KB Partially correct
20 Correct 15 ms 15428 KB Output is correct
21 Correct 15 ms 15476 KB Output is correct
22 Correct 23 ms 15932 KB Output is correct
23 Correct 17 ms 15428 KB Output is correct
24 Correct 18 ms 15428 KB Output is correct
25 Correct 18 ms 15412 KB Output is correct
26 Correct 19 ms 15424 KB Output is correct
27 Correct 19 ms 15412 KB Output is correct
28 Correct 19 ms 15416 KB Output is correct
29 Correct 17 ms 15068 KB Output is correct
30 Correct 17 ms 15408 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 17436 KB Output is correct
3 Correct 31 ms 17488 KB Output is correct
4 Incorrect 19 ms 15288 KB Output isn't correct
5 Halted 0 ms 0 KB -