답안 #946895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946895	2024-03-15T07:16:33 Z	shenfe1	Amusement Park (JOI17_amusement_park)	C++17	83 / 100	20 ms	5220 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);
    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);
}

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);
    // cout<<mxD<<"\n";
    if(mxD+1>=60){
      int cnt=0;
      while(P!=root&&(d[P]%60!=0||d[D[P]]-d[P]<59)){
        cnt++;
        if(cnt>120||P==-1){return -1;}
        V=Move(pr[P]);
        P=pr[P];
      }
      ans+=V*(1ll<<0);
      for(int i=1;i<60;i++){
        if(P==-1)return -1;
        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(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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1816 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	1808 KB	Output is correct
5	Correct	2 ms	1820 KB	Output is correct
6	Correct	1 ms	1800 KB	Output is correct
7	Correct	2 ms	1820 KB	Output is correct
8	Correct	2 ms	1824 KB	Output is correct
9	Correct	2 ms	1824 KB	Output is correct
10	Correct	1 ms	1808 KB	Output is correct
11	Correct	3 ms	2144 KB	Output is correct
12	Correct	1 ms	1812 KB	Output is correct
13	Correct	2 ms	1828 KB	Output is correct
14	Correct	2 ms	1828 KB	Output is correct
15	Correct	2 ms	1828 KB	Output is correct
16	Correct	2 ms	1824 KB	Output is correct
17	Correct	2 ms	1812 KB	Output is correct
18	Correct	1 ms	1828 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	4940 KB	Output is correct
2	Correct	18 ms	5024 KB	Output is correct
3	Correct	19 ms	4960 KB	Output is correct
4	Correct	14 ms	4312 KB	Output is correct
5	Correct	13 ms	4576 KB	Output is correct
6	Correct	12 ms	4804 KB	Output is correct
7	Correct	11 ms	4316 KB	Output is correct
8	Correct	12 ms	4316 KB	Output is correct
9	Correct	13 ms	4316 KB	Output is correct
10	Correct	11 ms	4576 KB	Output is correct
11	Correct	14 ms	4540 KB	Output is correct
12	Correct	11 ms	4044 KB	Output is correct
13	Correct	12 ms	4048 KB	Output is correct
14	Correct	11 ms	4044 KB	Output is correct
15	Correct	13 ms	4308 KB	Output is correct
16	Correct	12 ms	4312 KB	Output is correct
17	Correct	15 ms	4456 KB	Output is correct
18	Correct	11 ms	4312 KB	Output is correct
19	Correct	11 ms	4316 KB	Output is correct
20	Correct	9 ms	4516 KB	Output is correct
21	Correct	9 ms	4312 KB	Output is correct
22	Correct	11 ms	4308 KB	Output is correct
23	Correct	11 ms	4312 KB	Output is correct
24	Correct	11 ms	4292 KB	Output is correct
25	Correct	14 ms	4324 KB	Output is correct
26	Correct	13 ms	4308 KB	Output is correct
27	Correct	15 ms	4312 KB	Output is correct
28	Correct	14 ms	4324 KB	Output is correct
29	Correct	11 ms	4300 KB	Output is correct
30	Correct	11 ms	4232 KB	Output is correct
31	Correct	2 ms	1824 KB	Output is correct
32	Correct	2 ms	1804 KB	Output is correct
33	Correct	1 ms	1808 KB	Output is correct
34	Correct	1 ms	1824 KB	Output is correct
35	Correct	1 ms	1824 KB	Output is correct
36	Correct	1 ms	1812 KB	Output is correct
37	Correct	1 ms	1812 KB	Output is correct
38	Correct	1 ms	1812 KB	Output is correct
39	Correct	2 ms	1824 KB	Output is correct
40	Correct	1 ms	1824 KB	Output is correct
41	Correct	1 ms	1812 KB	Output is correct
42	Correct	1 ms	1812 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1824 KB	Output is correct
2	Correct	1 ms	1812 KB	Output is correct
3	Correct	1 ms	1808 KB	Output is correct
4	Correct	2 ms	2352 KB	Output is correct
5	Correct	2 ms	2360 KB	Output is correct
6	Correct	2 ms	2348 KB	Output is correct
7	Correct	2 ms	2352 KB	Output is correct
8	Correct	2 ms	2360 KB	Output is correct
9	Correct	10 ms	4824 KB	Output is correct
10	Correct	9 ms	4832 KB	Output is correct
11	Correct	10 ms	4920 KB	Output is correct
12	Correct	0 ms	1820 KB	Output is correct
13	Correct	2 ms	1812 KB	Output is correct
14	Correct	2 ms	1816 KB	Output is correct
15	Correct	2 ms	1820 KB	Output is correct

Subtask #4

55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	4964 KB	Output is correct
2	Correct	18 ms	4972 KB	Output is correct
3	Correct	19 ms	5108 KB	Output is correct
4	Correct	12 ms	4316 KB	Output is correct
5	Correct	11 ms	4580 KB	Output is correct
6	Correct	12 ms	4324 KB	Output is correct
7	Correct	11 ms	4308 KB	Output is correct
8	Correct	11 ms	4568 KB	Output is correct
9	Correct	11 ms	4316 KB	Output is correct
10	Correct	13 ms	4300 KB	Output is correct
11	Correct	13 ms	4320 KB	Output is correct
12	Correct	11 ms	4036 KB	Output is correct
13	Correct	11 ms	4132 KB	Output is correct
14	Correct	13 ms	4048 KB	Output is correct
15	Correct	12 ms	4308 KB	Output is correct
16	Correct	11 ms	4316 KB	Output is correct
17	Correct	11 ms	4316 KB	Output is correct
18	Correct	11 ms	4308 KB	Output is correct
19	Correct	13 ms	4224 KB	Output is correct
20	Correct	9 ms	4324 KB	Output is correct
21	Correct	9 ms	4288 KB	Output is correct
22	Correct	12 ms	4316 KB	Output is correct
23	Correct	12 ms	4308 KB	Output is correct
24	Correct	11 ms	4324 KB	Output is correct
25	Correct	15 ms	4316 KB	Output is correct
26	Correct	11 ms	4288 KB	Output is correct
27	Correct	12 ms	4320 KB	Output is correct
28	Correct	12 ms	4312 KB	Output is correct
29	Correct	11 ms	4544 KB	Output is correct
30	Correct	11 ms	4316 KB	Output is correct

Subtask #5

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	5004 KB	Output is correct
2	Correct	19 ms	4956 KB	Output is correct
3	Correct	20 ms	5160 KB	Output is correct
4	Correct	14 ms	4312 KB	Output is correct
5	Correct	13 ms	4924 KB	Output is correct
6	Correct	11 ms	4416 KB	Output is correct
7	Correct	13 ms	4420 KB	Output is correct
8	Correct	14 ms	4588 KB	Output is correct
9	Correct	13 ms	4420 KB	Output is correct
10	Correct	11 ms	4412 KB	Output is correct
11	Correct	13 ms	5220 KB	Output is correct
12	Correct	11 ms	4292 KB	Output is correct
13	Correct	11 ms	4128 KB	Output is correct
14	Correct	11 ms	4404 KB	Output is correct
15	Correct	11 ms	4420 KB	Output is correct
16	Correct	11 ms	4476 KB	Output is correct
17	Correct	12 ms	4304 KB	Output is correct
18	Correct	12 ms	4496 KB	Output is correct
19	Correct	13 ms	4408 KB	Output is correct
20	Correct	9 ms	4412 KB	Output is correct
21	Correct	9 ms	4416 KB	Output is correct
22	Correct	12 ms	4400 KB	Output is correct
23	Correct	11 ms	4416 KB	Output is correct
24	Correct	11 ms	4412 KB	Output is correct
25	Correct	11 ms	4232 KB	Output is correct
26	Correct	11 ms	4632 KB	Output is correct
27	Correct	13 ms	4416 KB	Output is correct
28	Correct	11 ms	4420 KB	Output is correct
29	Correct	11 ms	4392 KB	Output is correct
30	Correct	11 ms	4408 KB	Output is correct
31	Correct	1 ms	1808 KB	Output is correct
32	Correct	1 ms	2212 KB	Output is correct
33	Correct	1 ms	1828 KB	Output is correct
34	Correct	1 ms	2076 KB	Output is correct
35	Correct	2 ms	1812 KB	Output is correct
36	Correct	1 ms	1812 KB	Output is correct
37	Correct	1 ms	1824 KB	Output is correct
38	Incorrect	1 ms	1824 KB	Output isn't correct
39	Halted	0 ms	0 KB	-