Submission #238783

#TimeUsernameProblemLanguageResultExecution timeMemory
238783dualitySplit the Attractions (IOI19_split)C++14
46 / 100
168 ms43640 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 ---------- vi adjList[100000],adjList2[100000]; int parent[100000],size[100000],disc[100000],low[100000],fin[100000],num = 0; int doDFS(int u,int p) { int i; parent[u] = p,size[u] = 1,disc[u] = low[u] = num++; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (disc[v] == -1) { adjList2[u].pb(v),size[u] += doDFS(v,u); low[u] = min(low[u],low[v]); } else if (v != p) low[u] = min(low[u],disc[v]); } fin[u] = num; return size[u]; } pii x[3]; vi ans; int need,no; int doDFS2(int u) { if (need == 0) return 0; int i; ans[u] = x[0].second,need--; for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i]); return 0; } int doDFS3(int u) { if (need == 0) return 0; int i; ans[u] = x[1].second,need--; for (i = 0; i < adjList[u].size(); i++) { if (ans[adjList[u][i]] == x[2].second) doDFS3(adjList[u][i]); } return 0; } int doDFS4(int u) { if (need == 0) return 0; int i; if ((disc[u] >= disc[no]) && (disc[u] < fin[no])) return 0; ans[u] = x[0].second,need--; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (ans[v] == x[2].second) doDFS4(v); } return 0; } vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) { int i; x[0] = mp(a,1),x[1] = mp(b,2),x[2] = mp(c,3),sort(x,x+3); for (i = 0; i < p.size(); i++) { adjList[p[i]].pb(q[i]); adjList[q[i]].pb(p[i]); } for (i = 0; i < n; i++) disc[i] = low[i] = -1; doDFS(0,-1); int u = 0; while (1) { int h = -1; for (i = 0; i < adjList2[u].size(); i++) { int v = adjList2[u][i]; if ((h == -1) || (size[v] > size[h])) h = v; } if (size[h] >= x[0].first) u = h; else break; } ans.resize(n,x[2].second); if (n-size[u] >= x[1].first) { need = x[0].first,doDFS2(u); need = x[1].first,doDFS3(parent[u]); } else { no = u,need = x[0].first,doDFS4(0); for (i = 0; i < adjList2[u].size(); i++) { int v = adjList2[u][i]; if (low[v] < disc[u]) doDFS2(v); } if (need > 0) fill(ans.begin(),ans.end(),0); else need = x[1].first,doDFS3(u); } return ans; }

Compilation message (stderr)

split.cpp: In function 'int doDFS(int, int)':
split.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS2(int)':
split.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i]);
                 ~~^~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS3(int)':
split.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS4(int)':
split.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p.size(); i++) {
                 ~~^~~~~~~~~~
split.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList2[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~
split.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList2[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...