QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557746 | #9241. Sphinx | zhouhuanyi# | 3 | 20ms | 4076kb | C++17 | 4.1kb | 2024-09-11 11:15:55 | 2024-09-11 11:15:55 |
Judging History
answer
#include "sphinx.h"
#include<iostream>
#include<cstdio>
#include<vector>
#define N 250
using namespace std;
int n,srt,wcnt,depth[N+1],fa[N+1],rt[N+1],tong[N+1],tong2[N+1],length,length2,lg[N+1],st[N+1],leng,A[N+1],B[N+1],D[N+1],F[N+1];
vector<int>E[N+1];
bool used[N+1],vis[N+1];
int find(int x)
{
if (rt[x]==x) return x;
return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
rt[x]=y;
return;
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void dfs(int x)
{
if (!(depth[x]&1)) tong[++length]=x;
else tong2[++length2]=x;
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs(E[x][i]);
return;
}
int calc(int x,int type)
{
vector<int>v(n);
for (int i=0;i<n;++i) v[i]=n;
for (int i=0;i<n;++i) vis[i]=0;
if (!type)
{
for (int i=1;i<=x;++i) v[tong[i]]=-1;
}
else
{
for (int i=1;i<=x;++i) v[tong2[i]]=-1;
}
int d=perform_experiment(v),cnt=0;
for (int i=0;i<n;++i)
if (v[i]==n)
rt[i]=i,cnt++;
for (int i=0;i<n;++i)
if (v[i]==n)
{
for (int j=0;j<E[i].size();++j)
if (v[E[i][j]]==n&&find(i)!=find(E[i][j]))
unionn(find(i),find(E[i][j])),cnt--;
}
return d-cnt;
}
int calc2(int x,int type)
{
vector<int>v(n);
for (int i=0;i<n;++i) v[i]=n;
for (int i=0;i<n;++i) vis[i]=0;
if (!type)
{
for (int i=x;i<=length;++i) v[tong[i]]=-1;
}
else
{
for (int i=x;i<=length2;++i) v[tong2[i]]=-1;
}
int d=perform_experiment(v),cnt=0;
for (int i=0;i<n;++i)
if (v[i]==n)
rt[i]=i,cnt++;
for (int i=0;i<n;++i)
if (v[i]==n)
{
for (int j=0;j<E[i].size();++j)
if (v[E[i][j]]==n&&find(i)!=find(E[i][j]))
unionn(find(i),find(E[i][j])),cnt--;
}
return d-cnt;
}
int solve(int x,int type)
{
int d,cnt=0;
if (!type) d=A[x];
else d=B[x];
for (int i=0;i<n;++i) vis[i]=0;
for (int i=1;i<=leng;++i) vis[st[i]]=1;
for (int i=0;i<n;++i)
if (vis[i])
rt[i]=i,cnt++;
for (int i=0;i<n;++i)
if (vis[i])
{
for (int j=0;j<E[i].size();++j)
if (vis[E[i][j]]&&find(i)!=find(E[i][j]))
unionn(find(i),find(E[i][j])),cnt--;
}
return d-wcnt;
}
int get(int x,int type)
{
vector<int>v(n);
for (int i=0;i<n;++i) v[i]=n;
for (int i=0;i<n;++i) vis[i]=0;
if (!type)
{
for (int i=1;i<=x;++i)
{
v[tong[i]]=-1;
for (int j=0;j<E[tong[i]].size();++j)
if (fa[E[tong[i]][j]]==tong[i]||fa[tong[i]]==E[tong[i]][j])
vis[E[tong[i]][j]]=1;
}
}
else
{
for (int i=1;i<=x;++i)
{
v[tong2[i]]=-1;
for (int j=0;j<E[tong2[i]].size();++j)
if (fa[E[tong2[i]][j]]==tong2[i]||fa[tong2[i]]==E[tong2[i]][j])
vis[E[tong2[i]][j]]=1;
}
}
for (int i=1;i<=leng;++i) v[st[i]]=n;
for (int i=0;i<n;++i)
if (vis[i])
v[i]=srt;
int d=perform_experiment(v),cnt=0;
for (int i=0;i<n;++i)
if (v[i]==srt||v[i]==n)
rt[i]=i,cnt++;
for (int i=0;i<n;++i)
if (v[i]==srt||v[i]==n)
{
for (int j=0;j<E[i].size();++j)
if (v[E[i][j]]==v[i]&&find(i)!=find(E[i][j]))
unionn(find(i),find(E[i][j])),cnt--;
}
return d-cnt;
}
std::vector<int> find_colours(int SN, std::vector<int> X, std::vector<int> Y) {
vector<int>G(SN);
int ps;
n=SN;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
for (int i=0;i<X.size();++i) add(X[i],Y[i]);
fa[0]=-1,dfs(0);
for (int i=1;i<=length;++i) A[i]=calc(i,0),D[i]=calc2(i,0);
for (int i=1;i<=length2;++i) B[i]=calc(i,1),F[i]=calc2(i,1);
for (int i=0;i<n;++i)
{
srt=i,ps=leng=wcnt=0;
while (ps<=length&&get(length,0)!=solve(length,0))
{
for (int j=lg[length];j>=0;--j)
if (ps+(1<<j)<=length&&get(ps+(1<<j),0)==solve(ps+(1<<j),0))
ps+=(1<<j);
ps++;
if (ps<=length)
{
st[++leng]=tong[ps],wcnt=D[ps]!=D[ps+1],G[tong[ps]]=i;
if (wcnt) break;
}
}
}
for (int i=0;i<n;++i)
{
srt=i,ps=leng=wcnt=0;
while (ps<=length2&&get(length,1)!=solve(length,1))
{
for (int j=lg[length2];j>=0;--j)
if (ps+(1<<j)<=length2&&get(ps+(1<<j),1)==solve(ps+(1<<j),1))
ps+=(1<<j);
ps++;
if (ps<=length2)
{
st[++leng]=tong2[ps],wcnt=F[ps]!=F[ps+1],G[tong2[ps]]=i;
if (wcnt) break;
}
}
}
return G;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 1ms
memory: 3744kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 1 1978433568 2 1978433568 1 1978433568 1 1978433568 2
output:
877694080 -1 2 877694080 -1 2 877694080 2 -1 877694080 2 -1 877694080 -1 0 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 0 -1 877694080 1 -1 877694081 0 0
result:
ok #experiments: 10
Test #2:
score: 3
Accepted
time: 1ms
memory: 3812kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 1 1978433568 2 1978433568 2 1978433568 1 1978433568 1
output:
877694080 -1 2 877694080 -1 2 877694080 2 -1 877694080 2 -1 877694080 -1 0 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694080 1 -1 877694081 0 1
result:
ok #experiments: 10
Test #3:
score: 3
Accepted
time: 0ms
memory: 4076kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 1 1978433568 1 1978433568 1 1978433568 2
output:
877694080 -1 2 877694080 -1 2 877694080 2 -1 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 -1 1 877694080 0 -1 877694080 0 -1 877694080 1 -1 877694081 1 0
result:
ok #experiments: 10
Test #4:
score: 3
Accepted
time: 0ms
memory: 3884kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 1 1978433568 2 1978433568 1 1978433568 1
output:
877694080 -1 2 877694080 -1 2 877694080 2 -1 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694080 1 -1 877694081 1 1
result:
ok #experiments: 10
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 4076kb
input:
1978433568 50 49 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 19784335...
output:
877694080 -1 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 877694080 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 50 -1 5...
result:
wrong answer Vertices 1 and 2 do have the same color, but they do not in returned answer
Subtask #3:
score: 0
Wrong Answer
Test #34:
score: 0
Wrong Answer
time: 20ms
memory: 4068kb
input:
1978433568 250 249 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 ...
output:
877694080 -1 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250...
result:
wrong answer Vertices 1 and 2 do have the same color, but they do not in returned answer
Subtask #4:
score: 0
Runtime Error
Test #43:
score: 0
Runtime Error
input:
1978433568 250 31125 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 5...
output:
877694080 -1 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250...
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%