제출 #291094

#제출 시각아이디문제언어결과실행 시간메모리
291094alexandra_udristoiuSplit the Attractions (IOI19_split)C++14
100 / 100
176 ms17784 KiB
#include "split.h" #include<vector> #define DIM 100005 using namespace std; static int viz[DIM], t[DIM], ind[5], d[DIM], e[DIM], niv[DIM]; static vector<int> v[DIM], sol; static void dfs(int nod){ d[nod] = 1; e[nod] = niv[nod]; viz[nod] = 1; for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i]; if(viz[vecin] == 0){ niv[vecin] = niv[nod] + 1; t[vecin] = nod; dfs(vecin); d[nod] += d[vecin]; e[nod] = min(e[nod], e[vecin]); } else if(vecin != t[nod]){ e[nod] = min(e[nod], niv[vecin]); } } } static void dfs2(int nod, int ind, int &s, int nr){ if(s < nr){ sol[nod] = ind; s++; } else{ return; } for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i]; if(t[vecin] == nod){ dfs2(vecin, ind, s, nr); } } } static void dfs3(int nod, int ind, int &s, int nr){ if(s < nr){ sol[nod] = ind; s++; } else{ return; } for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i]; if(sol[vecin] == 0){ dfs3(vecin, ind, s, nr); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int i, j, sum, ok, sa, sb, nod, jj; ind[1] = 1; ind[2] = 2; ind[3] = 3; if(a > b){ swap(a, b); swap(ind[1], ind[2]); } if(a > c){ swap(a, c); swap(ind[1], ind[3]); } if(b > c){ swap(b, c); swap(ind[2], ind[3]); } for(i = 0; i < p.size(); i++){ v[ p[i] ].push_back(q[i]); v[ q[i] ].push_back(p[i]); } t[0] = -1; dfs(0); ok = 0; sol.resize(n); for(i = 1; i < n && ok == 0; i++){ sum = d[i]; for(j = 0; j < v[i].size(); j++){ if(sum >= a && n - sum >= b){ ok = 1; break; } nod = v[i][j]; if(t[nod] == i && e[nod] < niv[i]){ sum -= d[nod]; } } if(ok == 1){ sa = 1; sb = 0; sol[i] = ind[1]; for(jj = 0; jj < v[i].size(); jj++){ nod = v[i][jj]; if(t[nod] == i){ if(jj >= j || e[nod] >= niv[i]){ dfs2(nod, ind[1], sa, a); } } } dfs3(t[i], ind[2], sb, b); continue; } sum = d[i]; for(j = 0; j < v[i].size(); j++){ if(sum >= b && n - sum >= a){ ok = 1; break; } nod = v[i][j]; if(t[nod] == i && e[nod] < niv[i]){ sum -= d[nod]; } } if(ok == 1){ sb = 1; sa = 0; sol[i] = ind[2]; for(jj = 0; jj < v[i].size(); jj++){ nod = v[i][jj]; if(t[nod] == i){ if(jj >= j || e[nod] >= niv[i]){ dfs2(nod, ind[2], sb, b); } } } dfs3(t[i], ind[1], sa, a); } } if(ok == 1){ for(i = 0; i < n; i++){ if(sol[i] == 0){ sol[i] = ind[3]; } } } return sol; }

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'void dfs(int)':
split.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int, int&, int)':
split.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int, int&, int)':
split.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(i = 0; i < p.size(); i++){
      |                ~~^~~~~~~~~~
split.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
split.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(jj = 0; jj < v[i].size(); jj++){
      |                         ~~~^~~~~~~~~~~~~
split.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
split.cpp:124:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for(jj = 0; jj < v[i].size(); jj++){
      |                         ~~~^~~~~~~~~~~~~
#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...