Submission #68884

#TimeUsernameProblemLanguageResultExecution timeMemory
68884dualityAmusement Park (JOI17_amusement_park)C++14
100 / 100
39 ms5504 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #include "Joi.h" static int parent[10000]; static int find(int n) { if (parent[n] != n) parent[n] = find(parent[n]); return parent[n]; } static vi adjList[10000]; static int key[10000],nxt[10000],heavy[10000]; static int visited[10000]; static queue<int> Q; static int doDFS(int u,int p) { int i; int m = 1,mv = -1; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { int r = doDFS(v,u); if (r+1 > m) m = r+1,mv = v; } } nxt[u] = mv; if (m == 60) { key[u] = 1; return 0; } else return m; } static int num = 0; static int message[10000]; static int doDFS2(int u,int p,LLI X) { int i; if (num < 60) { MessageBoard(u,((X & (1LL << num)) > 0)); message[u] = 1; } num++; if (heavy[u] != -1) doDFS2(heavy[u],u,X); for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && (v != heavy[u])) doDFS2(v,u,X); } return 0; } void Joi(int N,int M,int A[],int B[],long long int X,int T) { int i; for (i = 0; i < N; i++) parent[i] = i; for (i = 0; i < M; i++) { int pa = find(A[i]),pb = find(B[i]); if (pa != pb) { parent[pa] = pb; adjList[A[i]].pb(B[i]); adjList[B[i]].pb(A[i]); } } int e = 0,e2 = 0; Q.push(0); while (!Q.empty()) { int u = Q.front(); Q.pop(); e = u; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (!visited[v]) { visited[v] = 1; Q.push(v); } } } fill(parent,parent+N,-1); fill(visited,visited+N,0); Q.push(e); while (!Q.empty()) { int u = Q.front(); Q.pop(); e2 = u; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (!visited[v]) { visited[v] = 1; parent[v] = u; Q.push(v); } } } fill(heavy,heavy+N,-1); while (e2 != e) heavy[parent[e2]] = e2,e2 = parent[e2]; int j,f = 0; doDFS(e,-1); for (i = 0; i < N; i++) { if (key[i]) { int u = i; for (j = 0; j < 60; j++) { MessageBoard(u,((X & (1LL << j)) > 0)); message[u] = 1; u = nxt[u]; } f = 1; } } if (!f) doDFS2(e,-1,X); for (i = 0; i < N; i++) { if (!message[i]) MessageBoard(i,0); } }
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #include "Ioi.h" static int parent[10000]; static int find(int n) { if (parent[n] != n) parent[n] = find(parent[n]); return parent[n]; } static vi adjList[10000]; static int key[10000],nxt[10000],heavy[10000]; static int visited[10000]; static queue<int> Q; static int doDFS(int u,int p) { int i; int m = 1,mv = -1; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { int r = doDFS(v,u); if (r+1 > m) m = r+1,mv = v; } } nxt[u] = mv; if (m == 60) { key[u] = 1; return 0; } else return m; } static int num = 0; static int sub[10000]; static int doDFS2(int u,int p) { int i; if (num < 60) sub[u] = num; num++; if (heavy[u] != -1) doDFS2(heavy[u],u); for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && (v != heavy[u])) doDFS2(v,u); } return 0; } static int message[10000]; static int moveto(int s,int e,int N) { int i,u; fill(parent,parent+N,-1); Q.push(s); while (!Q.empty()) { u = Q.front(); Q.pop(); if (key[u]) break; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != s) && (parent[v] == -1)) { parent[v] = u; Q.push(v); } } } while (!Q.empty()) Q.pop(); if (!key[u]) { u = e; vi path; while (u != -1) path.pb(u),u = parent[u]; if (sub[path.back()] != -1) return path.back(); for (i = (int) path.size()-2; i >= 0; i--) { message[path[i]] = Move(path[i]); if (sub[path[i]] != -1) return path[i]; } } vi path; while (u != -1) path.pb(u),u = parent[u]; for (i = (int) path.size()-2; i >= 0; i--) message[path[i]] = Move(path[i]); return path[0]; } static LLI ans = 0; static int path[10000]; static int doDFS3(int u,int e,int p) { int i; path[u] = 1; if (u == e) return 1; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { if (doDFS3(v,e,u)) return 1; } } path[u] = 0; return 0; } static int doDFS4(int u,int p) { int i; if (message[u]) ans |= (1LL << sub[u]); for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && !path[v] && (sub[v] != -1)) { message[v] = Move(v); doDFS4(v,u); Move(u); } } for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && path[v] && (sub[v] != -1)) { message[v] = Move(v); doDFS4(v,u); } } return 0; } long long int Ioi(int N,int M,int A[],int B[],int P,int V,int T) { int i; for (i = 0; i < N; i++) parent[i] = i; for (i = 0; i < M; i++) { int pa = find(A[i]),pb = find(B[i]); if (pa != pb) { parent[pa] = pb; adjList[A[i]].pb(B[i]); adjList[B[i]].pb(A[i]); } } int e = 0,e2 = 0; Q.push(0); while (!Q.empty()) { int u = Q.front(); Q.pop(); e = u; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (!visited[v]) { visited[v] = 1; Q.push(v); } } } fill(parent,parent+N,-1); fill(visited,visited+N,0); Q.push(e); while (!Q.empty()) { int u = Q.front(); Q.pop(); e2 = u; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (!visited[v]) { visited[v] = 1; parent[v] = u; Q.push(v); } } } fill(heavy,heavy+N,-1); while (e2 != e) heavy[parent[e2]] = e2,e2 = parent[e2]; fill(sub,sub+N,-1); doDFS(e,-1),doDFS2(e,-1); fill(message,message+N,-1); message[P] = V; int d = moveto(P,e,N); if (key[d]) { LLI X = 0; int u = d; for (i = 0; i < 60; i++) { if (message[u]) X |= (1LL << i); u = nxt[u]; if (i < 59) message[u] = Move(u); } return X; } else { doDFS3(d,e,-1),doDFS4(d,-1); return ans; } }

Compilation message (stderr)

Joi.cpp: In function 'int doDFS(int, int)':
Joi.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'int doDFS2(int, int, LLI)':
Joi.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:119:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
Joi.cpp:135:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~

Ioi.cpp: In function 'int doDFS(int, int)':
Ioi.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'int doDFS2(int, int)':
Ioi.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'int moveto(int, int, int)':
Ioi.cpp:108:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'int doDFS3(int, int, int)':
Ioi.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'int doDFS4(int, int)':
Ioi.cpp:150:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:185:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
Ioi.cpp:201:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].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...