제출 #1117917

#제출 시각아이디문제언어결과실행 시간메모리
1117917nai0610스핑크스 (IOI24_sphinx)C++17
0 / 100
47 ms584 KiB
#include "sphinx.h" #include <bits/stdc++.h> #define ll int64_t #define ld long double using namespace std; // const int maxn =1e5+5; const int mod = 1e9+7; // 998244353,1610612741 const ll inf = 1e18; const ld pi = atan(1.0L)*4; struct Dsu{ vector<int> par; void init(int n){ par.resize(n+5,0); for (int i=1;i<=n;i++) par[i]=i; } int find (int v){ if (par[v]==v) return v; return par[v]=find(par[v]); } bool join(int u,int v){ if ((u = find(u))==(v=find(v))) return false; par[v]=u; return true; } } dsu; vector<int> find_colours(int n,vector<int> x,vector<int> y) { dsu.init(n); vector<vector<int>> g(n); for (int i=0;i<x.size();i++) g[y[i]].push_back(x[i]); auto nai =[&](vector<int> v,int c) { int res=count(v.begin(),v.end(),c); Dsu cnt;cnt.init(n); for (int i=0;i<x.size();i++) { if (v[x[i]]==c&&v[y[i]]==c) res-=cnt.join(x[i],y[i]); } return res; }; for (int i=0;i<n;i++) { map<int,int> m; for (auto j:g[i]) m[dsu.find(j)]=j; if (m.size()==0) continue; vector<int> v; for (auto j:m) v.push_back(j.second); auto f =[&](int l,int r){ vector<int> u={i}; for (int j=l;j<r;j++) u.push_back(v[j]); vector<int> w(n,n); for (auto j:u) w[j]=-1; return perform_experiment(w)-nai(w,n); }; for (int j=0;j<v.size();j++) { if (f(j,v.size())==v.size()-j+1) break; int l=j,r=v.size(); while (l<=r) { int mid = (l+r)/2; if (f(j,mid)==mid-j+1) l=mid+1; else r=mid-1; } dsu.join(v[l-1],i); j=l; } } vector<vector<int>> adj(n); for (int i=0;i<x.size();i++) { int u =dsu.find(x[i]); int v =dsu.find(y[i]); if (u!=v) { adj[u].push_back(v); adj[v].push_back(u); } } vector<vector<int>> comp(n); for (int i=0;i<n;i++) comp[dsu.find(i)].push_back(i); int r=dsu.find(0); vector<int> ord[2]; vector<int> h(n),vs(n); queue<int> q; q.push(r); vs[r]=1; while (!q.empty()) { int u= q.front();q.pop(); ord[h[u]%2].push_back(u); for (auto v:adj[u]){ if (!vs[v]) { vs[v]=1; h[v]=h[u]+1; q.push(v); } } } vector<int> res(n,0); if (comp[r].size()==n) { for (int i=0;i<n;i++) { vector<int> v(n,i); v[0]=-1; if (perform_experiment(v)==1) { for (auto j:comp[r]) res[j]=i; break; } } return res; } for (int i=0;i<2;i++) { auto f =[&](int c,int l,int r){ vector<int> v(n,c); for (int j=0;j<n;j++) { if (!comp[j].empty()&&h[j]%2==i) { for (auto k:comp[j]) v[k]=n; } } for (int j=l;j<r;j++) { for (auto k:comp[ord[i][j]]) v[k]=-1; } return perform_experiment(v)-nai(v,c)-nai(v,n)<(r-l); }; for (int j=1;j<n;j++) { vector<int> a; for (int k=0;k<ord[i].size();) { if (!(f(j,k,ord[i].size()))) break; int l=k,r=ord[i].size(); while (l<=r) { int mid =(l+r)/2; if (f(j,k,mid)==mid-k+1) l=mid+1; else r=mid-1; } for (auto u:comp[ord[i][l-1]]) res[u]=j; a.push_back(l-1); k=l; } reverse(a.begin(),a.end()); for (auto x:a) ord[i].erase(ord[i].begin()+x); } } return res; }

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

sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i=0;i<x.size();i++) g[y[i]].push_back(x[i]);
      |               ~^~~~~~~~~
sphinx.cpp: In lambda function:
sphinx.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0;i<x.size();i++) {
      |                ~^~~~~~~~~
sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int j=0;j<v.size();j++) {
      |                ~^~~~~~~~~
sphinx.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if (f(j,v.size())==v.size()-j+1) break;
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
sphinx.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=0;i<x.size();i++) {
      |               ~^~~~~~~~~
sphinx.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  if (comp[r].size()==n) {
      |      ~~~~~~~~~~~~~~^~~
sphinx.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |    for (int k=0;k<ord[i].size();) {
      |                 ~^~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...