제출 #1048598

#제출 시각아이디문제언어결과실행 시간메모리
1048598NotLinuxSplit the Attractions (IOI19_split)C++17
100 / 100
143 ms24444 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x.size()) #define all(x) x.begin(), x.end() const int inf = 1e9 + 7; const int LIM1 = 1e5 + 7; int subt[LIM1] , N , A , B , C , vis[LIM1] , past[LIM1] , depth[LIM1] , high[LIM1]; vector < int > graph[LIM1] , color; vector < pair < int , int > > wlog(3); void dfs1(int node , int par){ subt[node] = 1; past[node] = par; depth[node] = depth[par] + 1; high[node] = depth[node]; // cout << "dfs1 : " << node << " , " << past[node] << endl; for(auto itr : graph[node]){ if(subt[itr] == -1){ dfs1(itr , node); subt[node] += subt[itr]; } else{ high[node] = min(high[node] , depth[itr]); } } } vector < set < int > > p(2); void vectorize(int node , int paint){ vis[node] = 1; p[paint].insert(node); for(auto itr : graph[node]){ if(past[itr] == node and vis[itr] == 0){ vectorize(itr , paint); } } } int balance = 0 , root = -1; int sayac0 , sayac1; void dfs2(int node){ if((subt[root] - balance - subt[node]) >= wlog[0].first and high[node] < depth[root]){ balance += subt[node]; vectorize(node , 1); } else{ for(auto itr : graph[node]){ if(past[itr] == node){ dfs2(itr); } } } } void dfs3(int node){ // cout << "dfs3 : " << node << endl; if(p[0].count(node) and sayac0){ // cout << "flag0 : " << sayac0 << endl; sayac0--; color[node] = wlog[0].second; } if(p[1].count(node) and sayac1){ // cout << "flag1 : " << sayac1 << endl; sayac1--; color[node] = wlog[1].second; } for(auto itr : graph[node]){ if(past[itr] == node){ dfs3(itr); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> ps, vector<int> qs) { N = n , A = a , B = b , C = c; memset(subt , -1 , sizeof(subt)); for(int i = 0;i<sz(ps);i++){ graph[ps[i]].push_back(qs[i]); graph[qs[i]].push_back(ps[i]); // cout << "edge : " << ps[i] << " " << qs[i] << endl; } wlog = {{A,0} , {B,1} , {C,2}}; sort(all(wlog)); depth[0] = 0; dfs1(0 , 0); color.assign(N , 0); for(int i = 0;i<n;i++){ if(subt[i] >= wlog[0].first){ bool bl = 1; for(auto itr : graph[i]){ if(past[itr] == i){ bl &= subt[itr] < wlog[0].first; } } if(bl == 0)continue; root = i; // cerr << "root : " << root << endl; dfs2(i); vectorize(root , 0); vectorize(0 , 1); // cout << "p0 : ";for(auto itr : p[0])cout << itr << " ";cout << endl; // cout << "p1 : ";for(auto itr : p[1])cout << itr << " ";cout << endl; if(p[0].size() > p[1].size())swap(p[0] , p[1]); if(p[0].size() < wlog[0].first){// fail return color; } color.assign(N , wlog[2].second); sayac0 = wlog[0].first , sayac1 = wlog[1].first; dfs3(0); for(int i = 0;i<n;i++)color[i]++; return color; } } return color; }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:100:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |             if(p[0].size() < wlog[0].first){// fail
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~
#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...