제출 #435771

#제출 시각아이디문제언어결과실행 시간메모리
435771Enkognit열쇠 (IOI21_keys)C++17
0 / 100
11 ms14412 KiB
#include <bits/stdc++.h> #define ll long long #define mp make_pair #define pb push_back #define all(v) v.begin(),v.end() #define fi first #define se second #define pll pair<ll,ll> #define pii pair<int,int> #define y1 Enkognit using namespace std; ll n, m, k, col[300001]; vector<pll> c[300001]; struct dsu { ll d[1000001]; void make_sets(int h) { for (int i = 0; i < h; i++) d[i]=i; } ll find_set(int h) { if (h==d[h]) return h; else return d[h]=find_set(d[h]); } bool unite_sets(int x,int y) { x=find_set(x); y=find_set(y); d[x]=y; return x!=y; } } g; vector<ll> vv[300001]; queue<ll> q; vector<ll> lst1, lst2, lst3; bool tt[300001], tl[300001], tu[300001]; void chk(int h) { tl[h]=1; lst2.pb(h); while (vv[h].size()) { if (!tt[vv[h].back()]) { tt[vv[h].back()]=1; q.push(vv[h].back()); } vv[h].pop_back(); } } void add(int h) { //q.push(h); chk(col[h]); lst1.pb(h); tt[h]=1; for (int i = 0; i < c[h].size(); i++) if (!tt[c[h][i].fi]) { if (tl[c[h][i].se]) { q.push(c[h][i].fi); tt[c[h][i].fi]=1; }else { if (!tu[c[h][i].se]) { tu[c[h][i].se]=1; lst3.pb(c[h][i].se); } vv[c[h][i].se].pb(c[h][i].fi); } } } vector<ll> bfs(int h) { q.push(h); tt[h]=1; vector<ll> ee; while (!q.empty()) { ll x=q.front(); q.pop(); ee.pb(x); //cout << x << " " << q.size() << "\n"; add(x); } while (lst1.size()) { tt[lst1.back()]=0; lst1.pop_back(); } while (lst2.size()) { tl[lst2.back()]=0; lst2.pop_back(); } while (lst3.size()) { tu[lst3.back()]=0; vv[lst3.back()].pop_back(); lst3.pop_back(); } return ee; } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> cc) { n=r.size(); for (int i = 0; i < n; i++) col[i]=r[i]; m=u.size(); g.make_sets(n); for (int i = 0; i < m; i++) { c[u[i]].pb(mp(v[i], cc[i])); c[v[i]].pb(mp(u[i], cc[i])); } vector<pll> merg; vector<vector<ll> > comp; do{ merg.clear(); for (int i = 0; i < n; i++) if (g.find_set(i)==i) { vector<ll> zz=bfs(i); if (g.find_set(zz.back())==g.find_set(i)) { comp.pb(zz); }else { merg.pb(mp(i, zz.back())); } } for (int j = 0; j < merg.size(); j++) { g.unite_sets(merg[j].fi, merg[j].se); //cout << merg[j].fi << " -> " << merg[j].se << "\n"; } //system("pause"); }while (merg.size()>0); ll mn=1e18; for (int i = 0; i < comp.size(); i++) mn=min(mn, (ll)comp[i].size()); vector<int> ans; ans.resize(n,0); for (int i = 0; i < comp.size(); i++) if (mn==comp[i].size()) { for (int j = 0; j < comp[i].size(); j++) ans[comp[i][j]]=1; } return ans; }

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

keys.cpp: In function 'void add(int)':
keys.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < c[h].size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:157:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         for (int j = 0; j < merg.size(); j++)
      |                         ~~^~~~~~~~~~~~~
keys.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:173:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:174:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         if (mn==comp[i].size())
      |             ~~^~~~~~~~~~~~~~~~
keys.cpp:176:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |             for (int j = 0; j < comp[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~
keys.cpp:173:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  173 |     for (int i = 0; i < comp.size(); i++)
      |     ^~~
keys.cpp:180:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  180 |  return ans;
      |  ^~~~~~
#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...