QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #557504 | #9241. Sphinx | zhouhuanyi# | 3 | 6ms | 4072kb | C++17 | 3.4kb | 2024-09-11 10:00:41 | 2024-09-11 10:00:41 |
answer
#include "sphinx.h"
#include<iostream>
#include<cstdio>
#include<vector>
#define N 250
using namespace std;
int n,srt,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];
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 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-cnt;
}
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);
for (int i=1;i<=length2;++i) B[i]=calc(i,1);
for (int i=0;i<n;++i)
{
srt=i,ps=leng=0;
while (ps<=length)
{
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],G[tong[ps]]=i;
}
}
for (int i=0;i<n;++i)
{
srt=i,ps=leng=0;
while (ps<=length2)
{
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],G[tong2[ps]]=i;
}
}
return G;
}
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 0ms
memory: 3812kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 1 1978433568 2 1978433568 1 1978433568 2
output:
877694080 -1 2 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694081 0 0
result:
ok #experiments: 6
Test #2:
score: 3
Accepted
time: 1ms
memory: 3788kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 1 1978433568 2 1978433568 2 1978433568 1
output:
877694080 -1 2 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694081 0 1
result:
ok #experiments: 6
Test #3:
score: 3
Accepted
time: 1ms
memory: 4040kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 1 1978433568 2
output:
877694080 -1 2 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694081 1 0
result:
ok #experiments: 6
Test #4:
score: 3
Accepted
time: 1ms
memory: 4072kb
input:
1978433568 2 1 0 1 1978433568 2 1978433568 2 1978433568 2 1978433568 1 1978433568 2 1978433568 1
output:
877694080 -1 2 877694080 2 -1 877694080 -1 0 877694080 -1 1 877694080 0 -1 877694080 1 -1 877694081 1 1
result:
ok #experiments: 6
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #5:
score: 7
Accepted
time: 5ms
memory: 3796kb
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 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 5...
result:
ok #experiments: 542
Test #6:
score: 7
Accepted
time: 4ms
memory: 3808kb
input:
1978433568 49 48 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 1978433568 2 1...
output:
877694080 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 877694080 -1 49 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 4...
result:
ok #experiments: 484
Test #7:
score: 7
Accepted
time: 5ms
memory: 3788kb
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 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 5...
result:
ok #experiments: 545
Test #8:
score: 7
Accepted
time: 4ms
memory: 3868kb
input:
1978433568 49 48 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 1978433568 2 1...
output:
877694080 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 877694080 -1 49 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 4...
result:
ok #experiments: 491
Test #9:
score: 7
Accepted
time: 0ms
memory: 3792kb
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 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 5...
result:
ok #experiments: 541
Test #10:
score: 7
Accepted
time: 1ms
memory: 3844kb
input:
1978433568 49 48 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 1978433568 2 1...
output:
877694080 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 877694080 -1 49 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 4...
result:
ok #experiments: 495
Test #11:
score: 7
Accepted
time: 0ms
memory: 3868kb
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 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 5...
result:
ok #experiments: 555
Test #12:
score: 7
Accepted
time: 5ms
memory: 4072kb
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 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 5...
result:
ok #experiments: 554
Test #13:
score: 7
Accepted
time: 0ms
memory: 3824kb
input:
1978433568 49 481 0 6 0 7 0 12 0 13 0 16 0 19 0 20 0 33 0 35 0 37 0 44 0 46 1 2 1 9 1 10 1 15 1 17 1 25 1 30 1 31 1 34 2 20 2 32 2 34 2 40 2 46 2 48 1 3 3 6 3 8 3 12 3 15 3 22 3 25 3 28 3 31 3 38 3 45 3 48 1 4 3 4 4 9 4 11 4 18 4 20 4 21 4 28 4 29 4 30 4 32 4 41 4 46 4 47 4 48 2 5 5 6 5 13 5 16 5 17...
output:
877694080 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 877694080 -1 49 49 -1 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 4...
result:
ok #experiments: 498
Test #14:
score: 7
Accepted
time: 6ms
memory: 3796kb
input:
1978433568 50 500 0 6 0 9 0 15 0 16 0 17 0 19 0 23 0 24 0 25 0 31 0 32 0 33 0 35 0 37 0 43 0 45 1 2 1 15 1 18 1 19 1 20 1 21 1 31 1 41 1 47 1 49 0 2 2 5 2 8 2 10 2 14 2 17 2 34 2 35 2 47 1 3 2 3 3 9 3 15 3 17 3 19 3 20 3 22 3 26 3 27 3 40 3 42 2 4 4 5 4 6 4 11 4 16 4 24 4 25 4 26 4 30 4 36 4 38 4 39...
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 50 50 -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 5...
result:
ok #experiments: 545
Test #15:
score: 7
Accepted
time: 5ms
memory: 3800kb
input:
1978433568 48 461 0 7 0 11 0 18 0 22 0 25 0 26 0 27 0 38 1 3 1 11 1 17 1 19 1 24 1 30 1 32 1 41 1 45 1 2 2 6 2 14 2 16 2 19 2 20 2 21 2 27 2 32 2 35 2 41 2 45 2 3 3 7 3 10 3 19 3 20 3 21 3 25 3 27 3 31 1 4 4 7 4 8 4 9 4 10 4 12 4 13 4 14 4 18 4 21 4 22 4 26 4 36 4 38 4 39 4 42 4 46 0 5 4 5 5 9 5 11 ...
output:
877694080 -1 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 877694080 -1 48 48 -1 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 4...
result:
ok #experiments: 458
Test #16:
score: 7
Accepted
time: 3ms
memory: 3892kb
input:
1978433568 50 500 0 4 0 16 0 17 0 21 0 23 0 27 0 40 0 47 1 6 1 15 1 20 1 31 1 33 1 34 1 35 1 38 1 47 1 49 2 11 2 19 2 20 2 23 2 28 2 30 2 34 2 36 3 15 3 16 3 20 3 22 3 29 3 33 3 35 3 36 3 39 3 42 3 48 3 49 1 4 2 4 4 10 4 13 4 21 4 28 4 30 4 32 4 35 4 40 4 43 4 44 4 5 5 14 5 24 5 34 5 35 5 42 5 44 5 ...
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 -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 5...
result:
ok #experiments: 550
Test #17:
score: 0
Wrong Answer
time: 5ms
memory: 3812kb
input:
1978433568 50 1225 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 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 1...
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 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 5...
result:
wrong answer Vertices 0 and 2 do have the same color, but they do not in returned answer
Subtask #3:
score: 0
Runtime Error
Test #34:
score: 0
Runtime Error
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:
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%