Submission #946932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
946932	2024-03-15T07:47:14 Z	shenfe1	Amusement Park (JOI17_amusement_park)	C++17	83 / 100	22 ms	5208 KB

Joi

#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=1e4+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:g1[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){
      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);
}

Ioi

#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=1e4+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=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);
        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]);
    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:g1[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);
    if(mxD+1>=60){
      while(d[D[P]]-d[P]<59){
        V=Move(pr[P]);
        P=pr[P];
      }
      ans+=V*(1ll<<(d[P]%60));
      for(int i=1;i<60;i++){
        if(P==-1)return -1;
        V=Move(big[P]);
        P=big[P];
        ans+=V*(1ll<<(d[P]%60));
      }
      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(pr[L]==P){
          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

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1816 KB	Output is correct
2	Correct	2 ms	1820 KB	Output is correct
3	Correct	2 ms	1824 KB	Output is correct
4	Correct	2 ms	1816 KB	Output is correct
5	Correct	2 ms	1804 KB	Output is correct
6	Correct	2 ms	1804 KB	Output is correct
7	Correct	1 ms	1824 KB	Output is correct
8	Correct	2 ms	1828 KB	Output is correct
9	Correct	2 ms	1824 KB	Output is correct
10	Correct	2 ms	1808 KB	Output is correct
11	Correct	3 ms	1868 KB	Output is correct
12	Correct	0 ms	2060 KB	Output is correct
13	Correct	2 ms	1812 KB	Output is correct
14	Correct	2 ms	1812 KB	Output is correct
15	Correct	2 ms	1820 KB	Output is correct
16	Correct	2 ms	1824 KB	Output is correct
17	Correct	2 ms	1824 KB	Output is correct
18	Correct	2 ms	1820 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	5068 KB	Output is correct
2	Correct	19 ms	4948 KB	Output is correct
3	Correct	18 ms	4964 KB	Output is correct
4	Correct	15 ms	4284 KB	Output is correct
5	Correct	12 ms	4576 KB	Output is correct
6	Correct	13 ms	4360 KB	Output is correct
7	Correct	14 ms	4312 KB	Output is correct
8	Correct	12 ms	4316 KB	Output is correct
9	Correct	12 ms	4116 KB	Output is correct
10	Correct	11 ms	4320 KB	Output is correct
11	Correct	12 ms	4312 KB	Output is correct
12	Correct	12 ms	4032 KB	Output is correct
13	Correct	13 ms	3948 KB	Output is correct
14	Correct	11 ms	4056 KB	Output is correct
15	Correct	11 ms	4320 KB	Output is correct
16	Correct	12 ms	4312 KB	Output is correct
17	Correct	12 ms	4320 KB	Output is correct
18	Correct	12 ms	4312 KB	Output is correct
19	Correct	12 ms	4316 KB	Output is correct
20	Correct	10 ms	4308 KB	Output is correct
21	Correct	10 ms	4196 KB	Output is correct
22	Correct	12 ms	4320 KB	Output is correct
23	Correct	12 ms	4516 KB	Output is correct
24	Correct	12 ms	4316 KB	Output is correct
25	Correct	11 ms	4316 KB	Output is correct
26	Correct	11 ms	4320 KB	Output is correct
27	Correct	13 ms	4576 KB	Output is correct
28	Correct	14 ms	4296 KB	Output is correct
29	Correct	12 ms	3996 KB	Output is correct
30	Correct	11 ms	4308 KB	Output is correct
31	Correct	1 ms	1816 KB	Output is correct
32	Correct	1 ms	1808 KB	Output is correct
33	Correct	2 ms	1816 KB	Output is correct
34	Correct	2 ms	1800 KB	Output is correct
35	Correct	1 ms	1824 KB	Output is correct
36	Correct	1 ms	1808 KB	Output is correct
37	Correct	1 ms	1808 KB	Output is correct
38	Correct	1 ms	1808 KB	Output is correct
39	Correct	1 ms	1820 KB	Output is correct
40	Correct	1 ms	1808 KB	Output is correct
41	Correct	1 ms	1812 KB	Output is correct
42	Correct	1 ms	1820 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1816 KB	Output is correct
2	Correct	2 ms	1808 KB	Output is correct
3	Correct	2 ms	1820 KB	Output is correct
4	Correct	3 ms	2352 KB	Output is correct
5	Correct	2 ms	2600 KB	Output is correct
6	Correct	3 ms	2356 KB	Output is correct
7	Correct	3 ms	2352 KB	Output is correct
8	Correct	2 ms	2352 KB	Output is correct
9	Correct	9 ms	4648 KB	Output is correct
10	Correct	9 ms	4824 KB	Output is correct
11	Correct	11 ms	4820 KB	Output is correct
12	Correct	1 ms	1820 KB	Output is correct
13	Correct	1 ms	1820 KB	Output is correct
14	Correct	1 ms	1816 KB	Output is correct
15	Correct	2 ms	1804 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	4964 KB	Output is correct
2	Correct	19 ms	4964 KB	Output is correct
3	Correct	22 ms	5048 KB	Output is correct
4	Correct	13 ms	4312 KB	Output is correct
5	Correct	12 ms	4552 KB	Output is correct
6	Correct	12 ms	4320 KB	Output is correct
7	Correct	11 ms	4312 KB	Output is correct
8	Correct	11 ms	4320 KB	Output is correct
9	Correct	13 ms	4312 KB	Output is correct
10	Correct	13 ms	4268 KB	Output is correct
11	Correct	13 ms	4520 KB	Output is correct
12	Correct	11 ms	4048 KB	Output is correct
13	Correct	11 ms	4176 KB	Output is correct
14	Correct	11 ms	4052 KB	Output is correct
15	Correct	12 ms	4056 KB	Output is correct
16	Correct	12 ms	4320 KB	Output is correct
17	Correct	13 ms	4564 KB	Output is correct
18	Correct	12 ms	4324 KB	Output is correct
19	Correct	12 ms	4568 KB	Output is correct
20	Correct	9 ms	4312 KB	Output is correct
21	Correct	10 ms	4320 KB	Output is correct
22	Correct	12 ms	4320 KB	Output is correct
23	Correct	12 ms	4324 KB	Output is correct
24	Correct	11 ms	4316 KB	Output is correct
25	Correct	12 ms	4568 KB	Output is correct
26	Correct	12 ms	4640 KB	Output is correct
27	Correct	11 ms	4320 KB	Output is correct
28	Correct	11 ms	4572 KB	Output is correct
29	Correct	11 ms	4040 KB	Output is correct
30	Correct	11 ms	4316 KB	Output is correct

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	4968 KB	Output is correct
2	Correct	19 ms	4960 KB	Output is correct
3	Correct	19 ms	5208 KB	Output is correct
4	Correct	14 ms	4320 KB	Output is correct
5	Correct	12 ms	4568 KB	Output is correct
6	Correct	12 ms	4308 KB	Output is correct
7	Correct	13 ms	4312 KB	Output is correct
8	Correct	12 ms	4328 KB	Output is correct
9	Correct	12 ms	4324 KB	Output is correct
10	Correct	11 ms	4304 KB	Output is correct
11	Correct	11 ms	4324 KB	Output is correct
12	Correct	11 ms	4040 KB	Output is correct
13	Correct	12 ms	4048 KB	Output is correct
14	Correct	11 ms	4048 KB	Output is correct
15	Correct	11 ms	4312 KB	Output is correct
16	Correct	11 ms	4316 KB	Output is correct
17	Correct	13 ms	4312 KB	Output is correct
18	Correct	12 ms	4324 KB	Output is correct
19	Correct	13 ms	4316 KB	Output is correct
20	Correct	9 ms	4308 KB	Output is correct
21	Correct	9 ms	4320 KB	Output is correct
22	Correct	12 ms	4312 KB	Output is correct
23	Correct	12 ms	4368 KB	Output is correct
24	Correct	12 ms	4312 KB	Output is correct
25	Correct	12 ms	4320 KB	Output is correct
26	Correct	12 ms	4312 KB	Output is correct
27	Correct	12 ms	4312 KB	Output is correct
28	Correct	14 ms	4276 KB	Output is correct
29	Correct	13 ms	4044 KB	Output is correct
30	Correct	11 ms	4304 KB	Output is correct
31	Correct	2 ms	1820 KB	Output is correct
32	Correct	2 ms	1820 KB	Output is correct
33	Correct	1 ms	2228 KB	Output is correct
34	Correct	1 ms	1820 KB	Output is correct
35	Correct	2 ms	1816 KB	Output is correct
36	Correct	2 ms	1820 KB	Output is correct
37	Correct	1 ms	1808 KB	Output is correct
38	Incorrect	1 ms	1816 KB	Output isn't correct
39	Halted	0 ms	0 KB	-