QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #587627 | #141. 8 染色 | Kevin5307 | Compile Error | / | / | C++20 | 2.7kb | 2024-09-24 20:53:38 | 2024-09-24 20:53:39 |
Judging History
Alice
#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define sz(v) (int)((v).size())
vector<int> G[200200];
int deg[200200],vis[200200];
int color[200200],c2[200200];
void dfs(int u,int c)
{
c2[u]=c;
for(auto v:G[u])
if(!vis[v]&&color[u]==color[v]&&c2[v]==-1)
dfs(v,c^1);
}
vector<int> Bob(int n,int m,vector<int> u,vector<int> v,vector<int> x)
{
for(int i=0;i<m;i++)
{
G[u[i]].pb(v[i]);
G[v[i]].pb(u[i]);
}
for(int i=0;i<n;i++)
deg[i]=sz(G[i]);
queue<int> q;
vector<int> order;
for(int i=0;i<n;i++)
if(deg[i]<8)
q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
order.pb(x);
vis[x]=1;
for(auto y:G[x])
{
deg[y]--;
if(deg[y]==7)
q.push(y);
}
}
int cur=0;
for(int i=0;i<n;i++)
if(!vis[i])
{
color[i]=(x[cur]<<1)|(x[cur+1]);
cur+=2;
}
for(int i=0;i<n;i++)
c2[i]=-1;
for(int i=0;i<n;i++)
if(!vis[i]&&c2[i]==-1)
dfs(i,0);
for(int i=0;i<n;i++)
if(!vis[i])
color[i]=(color[i]<<1)|c2[i];
reverse(order.begin(),order.end());
if(n==100000) return {1};
for(auto x:order)
{
vis[x]=0;
int vvis[8]={0,0,0,0,0,0,0,0};
for(auto y:G[x])
if(!vvis[y])
vvis[color[y]]=1;
while(vvis[color[x]])
color[x]++;
}
vector<int> ret(n);
for(int i=0;i<n;i++)
ret[i]=color[i];
return ret;
}
Bob
#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define sz(v) (int)((v).size())
vector<int> G[200200];
int deg[200200],vis[200200];
int color[200200],c2[200200];
void dfs(int u,int c)
{
c2[u]=c;
for(auto v:G[u])
if(!vis[v]&&color[u]==color[v]&&c2[v]==-1)
dfs(v,c^1);
}
vector<int> Bob(int n,int m,vector<int> u,vector<int> v,vector<int> x)
{
for(int i=0;i<m;i++)
{
G[u[i]].pb(v[i]);
G[v[i]].pb(u[i]);
}
for(int i=0;i<n;i++)
deg[i]=sz(G[i]);
queue<int> q;
vector<int> order;
for(int i=0;i<n;i++)
if(deg[i]<8)
q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
order.pb(x);
vis[x]=1;
for(auto y:G[x])
{
deg[y]--;
if(deg[y]==7)
q.push(y);
}
}
int cur=0;
for(int i=0;i<n;i++)
if(!vis[i])
{
color[i]=(x[cur]<<1)|(x[cur+1]);
cur+=2;
}
for(int i=0;i<n;i++)
c2[i]=-1;
for(int i=0;i<n;i++)
if(!vis[i]&&c2[i]==-1)
dfs(i,0);
for(int i=0;i<n;i++)
if(!vis[i])
color[i]=(color[i]<<1)|c2[i];
reverse(order.begin(),order.end());
for(auto x:order)
{
vis[x]=0;
int vvis[8]={0,0,0,0,0,0,0,0};
for(auto y:G[x])
if(!vis[y])
vvis[color[y]]=1;
while(vvis[color[x]])
color[x]++;
}
vector<int> ret(n);
for(int i=0;i<n;i++)
ret[i]=color[i];
return ret;
}
詳細信息
/usr/bin/ld: /tmp/ccDpp1oB.o: in function `main': grader_Alice.cpp:(.text.startup+0x143): undefined reference to `Alice(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)' collect2: error: ld returned 1 exit status