Submission #117452

#TimeUsernameProblemLanguageResultExecution timeMemory
117452dualityMeetings (JOI19_meetings)C++14
0 / 100
1911 ms17740 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 "meetings.h" int M[2000][2000]; bitset<2000> P[2000],C[2000]; int lca(int v,int w) { //cout<<"lca "<<v<<","<<w<<endl; if ((v == 0) || (w == 0)) return 0; else if (v == w) return v; if (M[v][w] != -1) return M[v][w]; else if (P[w][v] || C[v][w]) return v; else if (P[v][w] || C[w][v]) return w; else { M[v][w] = M[w][v] = Query(0,v,w); C[M[v][w]][v] = C[M[w][v]][w] = 1; P[v][M[v][w]] = P[w][M[v][w]] = 1; if (M[v][w] == v) P[w] |= P[v],C[v] |= C[w]; else if (M[v][w] == w) P[v] |= P[w],C[w] |= C[v]; else C[M[v][w]] |= C[v] | C[w]; return M[v][w]; } }/* int solve(vi v,int r,int N) { if (v.size() <= 1) return 0; int i,j; vector<vi> sub; vi child; for (i = 0; i < v.size(); i++) { int u = v[i]; if (u == r) continue; if (sub.empty()) sub.pb(vi()),sub[0].pb(u),child.pb(u); else { int k,c; vpii order; for (j = 0; j < sub.size(); j++) order.pb(mp(sub[j].size(),j)); sort(order.begin(),order.end(),greater<pii>()); for (j = 0; j < sub.size(); j++) { k = order[j].second; if ((c=lca(child[k],u,N)) != r) break; } if (j == sub.size()) sub.pb(vi()),sub.back().pb(u),child.pb(u); else sub[k].pb(u),child[k] = c; } } for (i = 0; i < sub.size(); i++) { if (r < child[i]) Bridge(r,child[i]); else Bridge(child[i],r); solve(sub[i],child[i],N); } return 0; }*/ vi adjList[2000]; int done[2000]; int parent[2000],size[2000],heavy[2000]; int chain[2000],head[2000],csize[2000],tail[2000],c = 0; int doDFS(int u,int p) { int i; parent[u] = p,size[u] = 1,heavy[u] = -1; //if (p != -1) cout<<"EDGE "<<u<<" "<<p<<endl; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { size[u] += doDFS(v,u); if ((heavy[u] == -1) || (size[v] > size[heavy[u]])) heavy[u] = v; } } return size[u]; } int doHLD(int u,int p) { int i; chain[u] = c,tail[c] = u; if (csize[c] == 0) head[c] = u; csize[c]++; if (heavy[u] != -1) doHLD(heavy[u],u); for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && (v != heavy[u])) c++,doHLD(v,u); } return 0; } int add(int u,int s) { int i; //cout<<"add "<<u<<" "<<s<<endl; if (heavy[s] == -1) { adjList[s].pb(u); adjList[u].pb(s); return 0; } int x = tail[chain[s]]; int v = lca(x,u); if (!done[v]) { vi path; int t = s; while (t != -1) path.pb(t),t = heavy[t]; int l = 1,r = path.size()-1; while (l < r) { int m = (l+r) / 2; if (lca(path[m],u) == v) r = m; else l = m+1; } //cout<<path[l-1]<<","<<path[l]<<endl; adjList[path[l-1]].erase(find(adjList[path[l-1]].begin(),adjList[path[l-1]].end(),path[l])); adjList[path[l]].erase(find(adjList[path[l]].begin(),adjList[path[l]].end(),path[l-1])); adjList[path[l]].pb(v),adjList[v].pb(path[l]); adjList[path[l-1]].pb(v),adjList[v].pb(path[l-1]); if (u != v) adjList[u].pb(v),adjList[v].pb(u); done[v] = 1; return 0; } else if (v == s) { for (i = 0; i < adjList[s].size(); i++) { int t = adjList[s][i]; if ((t == parent[s]) || (t == heavy[s])) continue; if (lca(tail[chain[t]],u) != s) { add(u,t); return 0; } } adjList[s].pb(u); adjList[u].pb(s); return 0; } else { vi path; int t = s; while (t != -1) path.pb(t),t = heavy[t]; int l = 1,r = path.size()-1; while (l < r) { int m = (l+r) / 2; if (lca(path[m],u) == v) r = m; else l = m+1; } add(u,path[l]); return 0; } } void Solve(int N) { int i; for (i = 0; i < N; i++) fill(M[i],M[i]+N,-1); done[0] = 1; for (i = 1; i < N; i++) { if (!done[i]) { doDFS(0,-1),c = 0,doHLD(0,-1),c++; //cout<<"here"<<endl; add(i,0); done[i] = 1; //cout<<"here"<<endl; //cout<<"fin "<<i<<endl; //for(int j=0;j<N;j++){ // for (int k =0;k<adjList[j].size();k++)cout<<j<<" "<<adjList[j][k]<<endl; //} } } doDFS(0,-1); for (i = 1; i < N; i++) { if (parent[i] < i) Bridge(parent[i],i); else Bridge(i,parent[i]); } }

Compilation message (stderr)

meetings.cpp: In function 'int doDFS(int, int)':
meetings.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'int doHLD(int, int)':
meetings.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'int add(int, int)':
meetings.cpp:166:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[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...