Submission #946911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
946911	2024-03-15T07:27:29 Z	shenfe1	Amusement Park (JOI17_amusement_park)	C++14	83 / 100	19 ms	5124 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]+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: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	2 ms	1808 KB	Output is correct
2	Correct	1 ms	1820 KB	Output is correct
3	Correct	2 ms	1820 KB	Output is correct
4	Correct	1 ms	1816 KB	Output is correct
5	Correct	1 ms	1804 KB	Output is correct
6	Correct	1 ms	1820 KB	Output is correct
7	Correct	2 ms	1816 KB	Output is correct
8	Correct	2 ms	1824 KB	Output is correct
9	Correct	1 ms	1820 KB	Output is correct
10	Correct	1 ms	1804 KB	Output is correct
11	Correct	3 ms	1860 KB	Output is correct
12	Correct	1 ms	1808 KB	Output is correct
13	Correct	1 ms	1816 KB	Output is correct
14	Correct	2 ms	1820 KB	Output is correct
15	Correct	2 ms	1820 KB	Output is correct
16	Correct	2 ms	1820 KB	Output is correct
17	Correct	2 ms	1804 KB	Output is correct
18	Correct	2 ms	1812 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	4964 KB	Output is correct
2	Correct	19 ms	4960 KB	Output is correct
3	Correct	19 ms	4952 KB	Output is correct
4	Correct	12 ms	4312 KB	Output is correct
5	Correct	12 ms	4572 KB	Output is correct
6	Correct	13 ms	4320 KB	Output is correct
7	Correct	13 ms	4312 KB	Output is correct
8	Correct	13 ms	4316 KB	Output is correct
9	Correct	12 ms	4336 KB	Output is correct
10	Correct	11 ms	4312 KB	Output is correct
11	Correct	11 ms	4312 KB	Output is correct
12	Correct	12 ms	4052 KB	Output is correct
13	Correct	12 ms	4556 KB	Output is correct
14	Correct	12 ms	4044 KB	Output is correct
15	Correct	11 ms	4316 KB	Output is correct
16	Correct	12 ms	4308 KB	Output is correct
17	Correct	13 ms	4240 KB	Output is correct
18	Correct	14 ms	4304 KB	Output is correct
19	Correct	12 ms	4312 KB	Output is correct
20	Correct	9 ms	4320 KB	Output is correct
21	Correct	12 ms	4312 KB	Output is correct
22	Correct	12 ms	4324 KB	Output is correct
23	Correct	13 ms	4320 KB	Output is correct
24	Correct	11 ms	4316 KB	Output is correct
25	Correct	13 ms	4300 KB	Output is correct
26	Correct	11 ms	4316 KB	Output is correct
27	Correct	12 ms	4312 KB	Output is correct
28	Correct	12 ms	4316 KB	Output is correct
29	Correct	13 ms	4044 KB	Output is correct
30	Correct	12 ms	4304 KB	Output is correct
31	Correct	1 ms	1808 KB	Output is correct
32	Correct	1 ms	1828 KB	Output is correct
33	Correct	2 ms	1828 KB	Output is correct
34	Correct	1 ms	2188 KB	Output is correct
35	Correct	1 ms	1808 KB	Output is correct
36	Correct	2 ms	1804 KB	Output is correct
37	Correct	1 ms	1820 KB	Output is correct
38	Correct	1 ms	1804 KB	Output is correct
39	Correct	1 ms	1808 KB	Output is correct
40	Correct	1 ms	1816 KB	Output is correct
41	Correct	1 ms	1816 KB	Output is correct
42	Correct	2 ms	1816 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1804 KB	Output is correct
2	Correct	2 ms	1808 KB	Output is correct
3	Correct	1 ms	1804 KB	Output is correct
4	Correct	2 ms	2348 KB	Output is correct
5	Correct	2 ms	2352 KB	Output is correct
6	Correct	3 ms	2352 KB	Output is correct
7	Correct	3 ms	2604 KB	Output is correct
8	Correct	3 ms	2352 KB	Output is correct
9	Correct	9 ms	4824 KB	Output is correct
10	Correct	10 ms	4832 KB	Output is correct
11	Correct	10 ms	4824 KB	Output is correct
12	Correct	0 ms	1808 KB	Output is correct
13	Correct	2 ms	1804 KB	Output is correct
14	Correct	1 ms	1812 KB	Output is correct
15	Correct	1 ms	1808 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	4960 KB	Output is correct
2	Correct	19 ms	4956 KB	Output is correct
3	Correct	18 ms	4964 KB	Output is correct
4	Correct	12 ms	4324 KB	Output is correct
5	Correct	13 ms	4580 KB	Output is correct
6	Correct	14 ms	4312 KB	Output is correct
7	Correct	13 ms	4312 KB	Output is correct
8	Correct	13 ms	4276 KB	Output is correct
9	Correct	13 ms	4308 KB	Output is correct
10	Correct	12 ms	4316 KB	Output is correct
11	Correct	11 ms	4324 KB	Output is correct
12	Correct	11 ms	4044 KB	Output is correct
13	Correct	11 ms	4052 KB	Output is correct
14	Correct	13 ms	4040 KB	Output is correct
15	Correct	12 ms	4312 KB	Output is correct
16	Correct	12 ms	4316 KB	Output is correct
17	Correct	12 ms	4312 KB	Output is correct
18	Correct	13 ms	4312 KB	Output is correct
19	Correct	12 ms	4316 KB	Output is correct
20	Correct	11 ms	4316 KB	Output is correct
21	Correct	10 ms	4320 KB	Output is correct
22	Correct	12 ms	4312 KB	Output is correct
23	Correct	16 ms	4284 KB	Output is correct
24	Correct	12 ms	4324 KB	Output is correct
25	Correct	11 ms	4300 KB	Output is correct
26	Correct	12 ms	4316 KB	Output is correct
27	Correct	12 ms	4312 KB	Output is correct
28	Correct	12 ms	4312 KB	Output is correct
29	Correct	11 ms	4048 KB	Output is correct
30	Correct	12 ms	4304 KB	Output is correct

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	5124 KB	Output is correct
2	Correct	19 ms	4960 KB	Output is correct
3	Correct	19 ms	4960 KB	Output is correct
4	Correct	13 ms	4312 KB	Output is correct
5	Correct	12 ms	4788 KB	Output is correct
6	Correct	13 ms	4312 KB	Output is correct
7	Correct	12 ms	4324 KB	Output is correct
8	Correct	12 ms	4460 KB	Output is correct
9	Correct	13 ms	4320 KB	Output is correct
10	Correct	11 ms	4320 KB	Output is correct
11	Correct	11 ms	4320 KB	Output is correct
12	Correct	16 ms	4128 KB	Output is correct
13	Correct	11 ms	4044 KB	Output is correct
14	Correct	12 ms	4056 KB	Output is correct
15	Correct	12 ms	4056 KB	Output is correct
16	Correct	13 ms	4272 KB	Output is correct
17	Correct	13 ms	4264 KB	Output is correct
18	Correct	13 ms	4324 KB	Output is correct
19	Correct	12 ms	4316 KB	Output is correct
20	Correct	10 ms	4324 KB	Output is correct
21	Correct	9 ms	4408 KB	Output is correct
22	Correct	12 ms	4324 KB	Output is correct
23	Correct	11 ms	4324 KB	Output is correct
24	Correct	12 ms	4312 KB	Output is correct
25	Correct	13 ms	4312 KB	Output is correct
26	Correct	12 ms	4268 KB	Output is correct
27	Correct	13 ms	4560 KB	Output is correct
28	Correct	12 ms	4316 KB	Output is correct
29	Correct	11 ms	4036 KB	Output is correct
30	Correct	11 ms	4304 KB	Output is correct
31	Correct	2 ms	1812 KB	Output is correct
32	Correct	1 ms	1820 KB	Output is correct
33	Correct	2 ms	1816 KB	Output is correct
34	Correct	1 ms	1816 KB	Output is correct
35	Correct	1 ms	1808 KB	Output is correct
36	Correct	0 ms	1804 KB	Output is correct
37	Correct	1 ms	1808 KB	Output is correct
38	Incorrect	2 ms	1804 KB	Output isn't correct
39	Halted	0 ms	0 KB	-