이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[300001];
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)
{
//cout << " chk " << h << " " << vv[h].size() << "\n";
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);
//cout << " add\n";
chk(col[h]);
//cout << " end chk\n";
lst1.pb(h);
tt[h]=1;
for (int i = 0; i < c[h].size(); i++)
if (!tt[c[h][i].fi])
{
//cout << "? " << c[h][i].fi << "\n";
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);
}
}
}
ll T=0;
vector<ll> bfs(int h)
{
q.push(h);
tt[h]=1;
vector<ll> ee;
//cout << " bfs\n";
while (!q.empty())
{
ll x=q.front();
//cout << x << "\n";
q.pop();
ee.pb(x);
//cout << x << "\n";
if (g.find_set(x)!=g.find_set(h)) T=x;
//cout << x << "\n";
add(x);
//cout << " " << x << " " << q.size() << "\n";
}
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()].clear();
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{
//cerr << "----\n";
merg.clear();
for (int i = 0; i < n; i++)
if (g.find_set(i)==i)
{
//cout << " " << i << " :\n";
T=-1;
vector<ll> zz=bfs(i);
//cout << "-\n";
if (T==-1)
{
comp.pb(zz);
}else
{
merg.pb(mp(i, T));
}
//cout << "--\n";
}
//cout << "!\n";
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);
//cout << "----\n";
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:71: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]
71 | 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:175: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]
175 | for (int j = 0; j < merg.size(); j++)
| ~~^~~~~~~~~~~~~
keys.cpp:187: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]
187 | for (int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
keys.cpp:193: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]
193 | for (int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
keys.cpp:194: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]
194 | if (mn==comp[i].size())
| ~~^~~~~~~~~~~~~~~~
keys.cpp:196:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int j = 0; j < comp[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~
keys.cpp:193:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
193 | for (int i = 0; i < comp.size(); i++)
| ^~~
keys.cpp:200:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
200 | return ans;
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |