Submission #49950

#TimeUsernameProblemLanguageResultExecution timeMemory
49950MatheusLealVAmusement Park (JOI17_amusement_park)C++17
100 / 100
52 ms8792 KiB
#include "Joi.h" #include <bits/stdc++.h> #define maxn 10005 #define f first #define s second using namespace std; typedef long long ll; typedef pair<int, int> pii; static int idx[maxn], pai[maxn], deep[maxn], cnt, maior; static vector<int> grafo[maxn], tree[maxn]; void dfs(int x) { idx[x] = cnt++; maior = max(maior, deep[x] + 1); for(auto v: grafo[x]) { if(idx[v] != -1) continue; pai[v] = x; deep[v] = deep[x] + 1; tree[x].push_back(v); tree[v].push_back(x); dfs(v); } } bool op2(int a, int b) { return (a*a) % 158987 < (b*b) % 158987; } void Joi(int N, int M, int A[], int B[], ll X, int T) { memset(idx, -1, sizeof idx); for(int i = 0; i < M; i++) { grafo[A[i]].push_back(B[i]); grafo[B[i]].push_back(A[i]); } for(int i = 0; i < N; i++) sort(grafo[i].begin(), grafo[i].end(),op2); dfs(0); if(maior >= 60) { for(int i = 0; i < N; i++) { deep[i] %= 60; if(X & (1LL<<deep[i])) MessageBoard(i, 1); else MessageBoard(i, 0); } } else { for(int i = 0; i < N; i++) { idx[i] = idx[i] % 60; if(X & (1LL<<idx[i])) MessageBoard(i, 1); else MessageBoard(i, 0); } } }
#include "Ioi.h" #include <bits/stdc++.h> #define maxn 10005 #define f first #define s second using namespace std; typedef long long ll; typedef pair<int, int> pii; static ll idx2[maxn], pai2[maxn], deep2[maxn], cnt2, maior2, dp[maxn]; static ll opt[maxn], ini[maxn], fim[maxn], save[maxn]; static vector<ll> grafo2[maxn], tree2[maxn], euler; static ll ans = 0; static set<ll> usados, tem[maxn]; void dfs2(int x) { idx2[x] = cnt2++; euler.push_back(x); maior2 = max(maior2, deep2[x] + 1); dp[x] = 0; for(auto v: grafo2[x]) { if(idx2[v] != -1) continue; pai2[v] = x; deep2[v] = deep2[x] + 1; tree2[x].push_back(v); tree2[v].push_back(x); dfs2(v); euler.push_back(x); if(dp[v] + 1 > dp[x]) dp[x] = dp[v] + 1, opt[x] = v; } } bool op(int a, int b) { return (a*a) % 158987 < (b*b) % 158987; } ll Ioi(int N, int M, int A[], int B[], int P, int V, int T) { memset(idx2, -1, sizeof idx2); int Vo = V; for(int i = 0; i < M; i++) { grafo2[A[i]].push_back(B[i]); grafo2[B[i]].push_back(A[i]); } for(int i = 0; i < N; i++) sort(grafo2[i].begin(), grafo2[i].end(), op); dfs2(0); if(maior2 >= 60) { usados.insert(deep2[P] % 60); if(V) ans += (1LL<< (deep2[P]%60) ); while(P != 0 and usados.size() < 60) { ll val = Move(pai2[P]), aux = deep2[pai2[P]]%60; if(val && !usados.count(aux)) ans += (1LL<< (aux) ); usados.insert(aux); P = pai2[P]; } if(usados.size() >= 60) return ans; while(usados.size() < 60) { ll val = Move(opt[P]), aux = deep2[opt[P]]%60; if(val && !usados.count(aux)) ans += (1LL<< (aux) ); usados.insert(aux); P = opt[P]; } return ans; } for(int i = 0; i < N; i++) idx2[i] = (idx2[i] % 60); ll t = 0, save; for(int i = 0; i < euler.size(); i++) { if(euler[i] == P) { t = save = i; break; } } ll pos = 0; pos |= (1LL<<idx2[P]); t ++; for(int cnt = 0; cnt < 120 ; cnt ++) { if(t >= euler.size() - 1) t = 0; ll x = euler[t]; pos |= (1LL<<idx2[x]); t ++; } //cout<<pos<<" "<<((1LL<<60) - 1LL)<<"\n"; int limite = (T == 2 ? 500 : 120); if(pos == ((1LL<<60) - 1LL)) { if(Vo) ans |= (1LL<<idx2[P]); t = save + 1; for(int cnt = 0; cnt < limite ; cnt ++) { if(t >= euler.size() - 1) t = 0; ll x = euler[t]; V = Move(x); if(V) ans |= (1LL<<idx2[x]); t ++; } //cout<<ans<<"\n"; return ans; } else { //for(auto tt: euler) cout<<tt<<" "; //cout<<"\n"; if(Vo) ans |= (1LL<<idx2[P]); t = save - 1; ll aux = 1LL<<idx2[P]; for(int cnt = 0; cnt < limite; cnt ++) { if(t <= 0) t = euler.size() - 1; ll x = euler[t]; V = Move(x); aux |= (1LL<<idx2[x]); if(V) ans |= (1LL<<idx2[x]); t --; } //cout<<aux<<" "<<((1LL<<60) - 1LL)<<"\n"; return ans; } }

Compilation message (stderr)

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < euler.size(); i++)
                 ~~^~~~~~~~~~~~~~
Ioi.cpp:127:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t >= euler.size() - 1) t = 0;
      ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp:148:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(t >= euler.size() - 1) t = 0;
       ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: At global scope:
Ioi.cpp:12:44: warning: 'save' defined but not used [-Wunused-variable]
 static ll opt[maxn], ini[maxn], fim[maxn], save[maxn];
                                            ^~~~
Ioi.cpp:12:33: warning: 'fim' defined but not used [-Wunused-variable]
 static ll opt[maxn], ini[maxn], fim[maxn], save[maxn];
                                 ^~~
Ioi.cpp:12:22: warning: 'ini' defined but not used [-Wunused-variable]
 static ll opt[maxn], ini[maxn], fim[maxn], save[maxn];
                      ^~~
Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:144:5: warning: 'save' may be used uninitialized in this function [-Wmaybe-uninitialized]
   t = save + 1;
   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...