Submission #93292

#TimeUsernameProblemLanguageResultExecution timeMemory
93292Alexa2001Amusement Park (JOI17_amusement_park)C++17
10 / 100
35 ms5324 KiB
#include "Joi.h" #include <bits/stdc++.h> typedef long long ll; const int Nmax = 30005; using namespace std; static bool used[Nmax]; static vector<int> v[Nmax]; static int bit, w[Nmax], t[Nmax]; static ll TO; static void dfs_sel_edges(int node) { used[node] = 1; w[node] = 1; for(auto it : v[node]) if(!used[it]) { t[it] = node; dfs_sel_edges(it); w[node] += w[it]; } } static void dfs(int node) { MessageBoard(node, (TO >> bit) & 1); for(auto it : v[node]) { bit = (bit+1) % 60; dfs(it); } } static bool cmp(int a, int b) { return w[a] < w[b]; } void Joi(int N, int M, int A[], int B[], ll X, int _T) { int i; TO = X; for(i=0; i<M; ++i) { v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); } t[0] = -1; dfs_sel_edges(0); vector<int> good; for(i=0; i<N; ++i) { good.clear(); for(auto it : v[i]) if(t[it] == i) good.push_back(it); v[i] = good; } for(i=0; i<N; ++i) sort(v[i].begin(), v[i].end(), cmp); bit = 0; dfs(0); }
#include "Ioi.h" #include <bits/stdc++.h> typedef long long ll; const int Nmax = 30005; const ll AllBits = (1LL << 60) - 1; using namespace std; static bool used[Nmax], to_visit[Nmax]; static vector<int> v[Nmax]; static int bit, w[Nmax], t[Nmax], In[Nmax], ord[Nmax], tip[Nmax], tmp, Special; ll Act, Mask; static void dfs_sel_edges(int node) { used[node] = 1; w[node] = 1; for(auto it : v[node]) if(!used[it]) { t[it] = node; dfs_sel_edges(it); w[node] += w[it]; } } static void dfs(int node) { tip[node] = bit; In[node] = ++tmp; ord[tmp] = node; for(auto it : v[node]) { bit = (bit+1) % 60; dfs(it); ord[++tmp] = node; } } bool cmp(int a, int b) { return w[a] < w[b]; } static void go(int node) { to_visit[node] = 0; for(auto it : v[node]) if(to_visit[it]) { Act |= (1LL<<tip[it]) * Move(it); go(it); Move(node); } if(node != 0 && to_visit[t[node]]) { Act |= (1LL<<tip[t[node]]) * Move(t[node]); go(t[node]); } } static ll baga(int node) { int i; for(i=In[node]; (!to_visit[Special] || Mask != AllBits) && i <= tmp; ++i) to_visit[ord[i]] = 1, Mask |= (1LL << tip[ord[i]]); assert(to_visit[Special] && Mask == AllBits); go(Special); return Act; } ll Ioi(int N, int M, int A[], int B[], int P, int V, int _T) { Special = P; int i; for(i=0; i<M; ++i) { v[A[i]].push_back(B[i]); v[B[i]].push_back(A[i]); } dfs_sel_edges(0); vector<int> good; for(i=0; i<N; ++i) { good.clear(); for(auto it : v[i]) if(it && t[it] == i) good.push_back(it); sort(good.begin(), good.end()); good.erase(unique(good.begin(), good.end()), good.end()); v[i] = good; } for(i=0; i<N; ++i) sort(v[i].begin(), v[i].end(), cmp); bit = 0; dfs(0); Mask = (1LL << tip[P]); Act = V * (1LL << tip[P]); int node = P, sbrb = -1; while(w[node] < 60) sbrb = node, node = t[node]; // return baga(node); if(node == P) return baga(P); assert(sbrb != -1); vector<int> S; bool ok = 0; int T = 0; for(i=0; i<v[node].size(); ++i) if(v[node][i] == sbrb) ok = 1; else if(!ok) S.push_back(w[v[node][i]]); else T += w[v[node][i]]; for(i=(int)S.size()-2; i>=0; --i) S[i] += S[i+1]; for(i=0; i<S.size(); ++i) if(S[i] + w[sbrb] <= 60 && S[i] + w[sbrb] + T >= 60) return baga(v[node][i]); if(w[sbrb] <= 60 && w[sbrb] + T >= 60) return baga(sbrb); assert(T == 0); for(i=S.size()-1; i>=0; --i) if(S[i] + w[sbrb] >= 60) baga(v[node][i]); return baga(node); }

Compilation message (stderr)

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
Ioi.cpp:131:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<S.size(); ++i)
              ~^~~~~~~~~
#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...