QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #217363 | #6109. Similarity Graph | ucup-team1004 | WA | 1ms | 3860kb | C++14 | 1.8kb | 2023-10-16 20:02:27 | 2023-10-16 20:02:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=1e2+10,V=N*N;
int n,m,a[N][N],id[N][N];
int p[N],q[N],fa[V];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return 0;
return fa[x]=y,1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i^j)id[i][j]=++m;
}
}
iota(fa,fa+1+m,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
for(int k=1;k<=n;k++){
if(a[i][k]!=a[i][j]||j==k||i==k)continue;
if(a[j][k]==a[i][j])merge(id[j][i],id[i][k]),merge(id[j][i],id[j][k]);
else merge(id[i][j],id[i][k]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(find(id[i][j])==find(id[j][i])){
puts("NO"),exit(0);
}
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i][j]){
if(find(id[i][j])<find(id[j][i])){
p[j]++,q[j]++;
}else{
p[i]++,q[i]++;
}
}else{
if(find(id[i][j])<find(id[j][i])){
p[j]++,q[i]++;
}else{
p[i]++,q[j]++;
}
}
}
}
puts("YES");
for(int i=1;i<=n;i++)printf("%d%c",p[i]+1,"\n "[i<n]);
for(int i=1;i<=n;i++)printf("%d%c",q[i]+1,"\n "[i<n]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
output:
YES 1 2 3 4 2 4 1 3
result:
ok ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
6 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0
output:
NO
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
1 0
output:
YES 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
2 0 1 1 0
output:
YES 1 2 1 2
result:
ok ok
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3744kb
input:
3 0 0 0 0 0 0 0 0 0
output:
NO
result:
wrong answer P did not found the answer