Submission #64241

#TimeUsernameProblemLanguageResultExecution timeMemory
64241realityAmusement Park (JOI17_amusement_park)C++17
100 / 100
966 ms242792 KiB
#include "Joi.h" #include "bits/stdc++.h" using namespace std; #define fi first #define se second #define ll long long #define dbg(v) cerr<<#v<<" = "<<v<<'\n' #define vi vector<int> #define vl vector <ll> #define pii pair<int,int> #define mp make_pair #define db long double #define pb push_back #define all(s) s.begin(),s.end() template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;} template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;} template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;} const int N = 1e4 + 5; const int C = 60; static vi g[N]; static set < int > G[N]; static int color[N]; static int f[N]; static int deg[N]; static int get(int k) { return k == f[k] ? k : f[k] = get(f[k]); } static int n; static void dfs(int node,int prev,set < int > nodes,set < pii > degs) { for (auto it : g[node]) if (it != prev) { if (nodes.count(it)) dfs(it,node,nodes,degs); else { set < int > new_nodes; set < pii > new_degs; for (auto w : nodes) new_nodes.insert(w); int u,v; auto low = degs.begin(); if (low->se == node) ++low; u = low->se; for (auto w : nodes) if (G[u].count(w)) { v = w; break; } new_nodes.erase(u); new_nodes.insert(it); color[it] = color[u]; --deg[u]; --deg[v]; ++deg[node]; ++deg[it]; for (auto it : new_nodes) new_degs.insert(mp(deg[it],it)); dfs(it,node,new_nodes,new_degs); ++deg[u]; ++deg[v]; --deg[node]; --deg[it]; } } } void Joi(int N, int M, int A[], int B[], long long X, int T) { n = N; for (int i = 0;i < n;++i) f[i] = i,color[i] = -1; for (int i = 0;i < M;++i) { if (get(A[i]) == get(B[i])) continue; g[A[i]].pb(B[i]); g[B[i]].pb(A[i]); G[A[i]].insert(B[i]); G[B[i]].insert(A[i]); f[get(A[i])] = get(B[i]); } set < int > nodes; set < pii > degs; queue < int > Q; int TT = -1; Q.push(0); while (!Q.empty()) { int node = Q.front(); Q.pop(); nodes.insert(node); color[node] = ++TT; if (nodes.size() == C) break; for (auto it : g[node]) if (!nodes.count(it)) { Q.push(it); } } for (auto u : nodes) for (auto v : g[u]) if (nodes.count(v) && u < v) ++deg[u],++deg[v]; for (auto it : nodes) degs.insert(mp(deg[it],it)); dfs(0,-1,nodes,degs); for (int i = 0;i < n;++i) MessageBoard(i,(X >> color[i]) & 1); }
#include "Ioi.h" #include "bits/stdc++.h" using namespace std; #define fi first #define se second #define ll long long #define dbg(v) cerr<<#v<<" = "<<v<<'\n' #define vi vector<int> #define vl vector <ll> #define pii pair<int,int> #define mp make_pair #define db long double #define pb push_back #define all(s) s.begin(),s.end() template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;} template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;} template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;} const int N = 1e4 + 5; const int C = 60; static vi g[N]; static set < int > G[N]; static int color[N]; static int f[N]; static int deg[N]; static int get(int k) { return k == f[k] ? k : f[k] = get(f[k]); } static int POS; static int n; static int was[N]; static void dfs(int node,int prev,set < int > nodes,set < pii > degs) { if (node == POS) { POS = -1; for (auto it : nodes) was[it] = 1; } for (auto it : g[node]) if (it != prev) { if (nodes.count(it)) dfs(it,node,nodes,degs); else { set < int > new_nodes; set < pii > new_degs; for (auto w : nodes) new_nodes.insert(w); int u,v; auto low = degs.begin(); if (low->se == node) ++low; u = low->se; for (auto w : nodes) if (G[u].count(w)) { v = w; break; } new_nodes.erase(u); new_nodes.insert(it); color[it] = color[u]; --deg[u]; --deg[v]; ++deg[node]; ++deg[it]; for (auto it : new_nodes) new_degs.insert(mp(deg[it],it)); dfs(it,node,new_nodes,new_degs); ++deg[u]; ++deg[v]; --deg[node]; --deg[it]; } } } static ll answer = 0; vi e; static void DFS(int node,int prev) { if (prev != -1) { e.pb(node); } for (auto it : g[node]) if (it != prev && was[it]) { DFS(it,node); e.pb(node); } } long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) { n = N; for (int i = 0;i < n;++i) f[i] = i,color[i] = -1; for (int i = 0;i < M;++i) { if (get(A[i]) == get(B[i])) continue; g[A[i]].pb(B[i]); g[B[i]].pb(A[i]); G[A[i]].insert(B[i]); G[B[i]].insert(A[i]); f[get(A[i])] = get(B[i]); } set < int > nodes; set < pii > degs; queue < int > Q; int TT = -1; Q.push(0); while (!Q.empty()) { int node = Q.front(); Q.pop(); nodes.insert(node); color[node] = ++TT; if (nodes.size() == C) break; for (auto it : g[node]) if (!nodes.count(it)) { Q.push(it); } } POS = P; for (auto u : nodes) for (auto v : g[u]) if (nodes.count(v) && u < v) ++deg[u],++deg[v]; for (auto it : nodes) degs.insert(mp(deg[it],it)); dfs(0,-1,nodes,degs); POS = P; DFS(P,-1); answer |= (1ll << color[P]) * V; for (auto it : e) answer |= (1ll << color[it]) * Move(it); return answer; }

Compilation message (stderr)

Joi.cpp: In function 'void dfs(int, int, std::set<int>, std::set<std::pair<int, int> >)':
Joi.cpp:69:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 ++deg[v];
                 ^~~~~~~~

Ioi.cpp: In function 'void dfs(int, int, std::set<int>, std::set<std::pair<int, int> >)':
Ioi.cpp:78:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 ++deg[v];
                 ^~~~~~~~
#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...