QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#146403 | #6329. Colorful Graph | PhantomThreshold# | WA | 6ms | 4428kb | C++20 | 2.0kb | 2023-08-22 15:50:06 | 2023-08-22 15:50:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<vector<int>> G(n+5);
vector<pair<int,int>> edges;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
edges.emplace_back(u,v);
}
vector<int> ins(n+5),bel(n+5),dfn(n+5),low(n+5);
stack<int> st;
int bcnt=0,ind=0;
function<void(int)> dfs=[&](int u)
{
dfn[u]=low[u]=++ind;
ins[u]=1;
st.push(u);
for(auto v:G[u])
{
if(not ins[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]==1)
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
int v;
++bcnt;
do
{
v=st.top();st.pop();
ins[v]=2;
bel[v]=bcnt;
}
while(u!=v);
}
};
for(int i=1;i<=n;i++)
{
if(not ins[i])
{
dfs(i);
}
}
G.clear();
G.resize(bcnt+bcnt+5);
for(auto &[u,v]:edges)
{
if(bel[u]!=bel[v])
{
// addedge(bel[u],bel[v]+bcnt);
G[bel[u]].push_back(bel[v]+bcnt);
}
}
vector<int> pa(bcnt+5);
function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
vector<int> ma(bcnt+bcnt+5),vis(bcnt+bcnt+5);
for(int i=1;i<=bcnt;i++)
{
for(auto v:G[i])
{
if(not ma[v])
{
ma[i]=v,ma[v]=i;
break;
}
}
}
// cerr<<"1111"<<endl;
function<bool(int)> augment=[&](int u)
{
vis[u]=1;
for(auto v:G[u])
{
if(not ma[v] or (not vis[ma[v]] and augment(ma[v])))
{
ma[u]=v;ma[v]=u;
return true;
}
}
return false;
};
for(int i=1;i<=bcnt;i++)
{
if(not ma[i])
{
fill(vis.begin(),vis.end(),0);
augment(ma[i]);
}
}
for(int i=1;i<=bcnt;i++)
{
if(ma[i])
{
int pu=find(i),pv=find(ma[i]-bcnt);
if(pu!=pv)
{
pa[pv]=pu;
}
}
}
vector<int> col(bcnt+5);
int ccol=0;
for(int i=1;i<=bcnt;i++)
{
if(find(i)==i)
{
col[i]=++ccol;
}
}
for(int i=1;i<=n;i++)
{
cout<<col[find(bel[i])]<<" \n"[i==n];
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
input:
5 5 1 4 2 3 1 3 2 5 5 1
output:
1 2 2 1 1
result:
ok AC
Test #2:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
5 7 1 2 2 1 4 3 5 1 5 4 4 1 4 5
output:
1 1 2 2 2
result:
ok AC
Test #3:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
8 6 6 1 3 4 3 6 2 3 4 1 6 4
output:
1 1 1 1 2 1 3 4
result:
ok AC
Test #4:
score: -100
Wrong Answer
time: 6ms
memory: 4428kb
input:
7000 6999 4365 4296 2980 3141 6820 4995 4781 24 2416 5844 2940 2675 3293 2163 3853 5356 262 6706 1985 1497 5241 3803 353 1624 5838 4708 5452 3019 2029 6161 3849 4219 1095 1453 4268 4567 1184 1857 2911 3977 1662 2751 6353 6496 2002 6628 1407 4623 425 1331 4445 4277 1259 3165 4994 1044 2756 5788 5496 ...
output:
1750 1551 913 1363 1752 1751 1752 990 459 1259 1750 1750 1753 1750 1289 1754 725 1755 361 1711 760 591 1752 1247 1561 1756 1757 1755 1076 1758 579 633 1759 1760 976 976 1173 1761 1752 1762 1297 546 1763 696 1764 389 1765 1752 1766 1767 17 1768 836 1752 1527 1390 1750 1769 292 1770 619 1752 1752 1752...
result:
wrong answer Integer 1752 violates the range [1, 1750]