QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #376516 | #6109. Similarity Graph | 369Pai | WA | 0ms | 3616kb | C++14 | 2.0kb | 2024-04-04 11:12:06 | 2024-04-04 11:12:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105 , M = 10005;
int n , m , a[N][N] , x[N] , y[N];
int fa[M] , in[N]; bool vis[M];
vector<int>g[N];
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
void BFS(int x[])
{
queue<int>q;
for(int i = 1 ; i <= n ; i++)
if(!in[i])q.push(i);
for(int i = 1 ; i <= n && !q.empty() ; i++)
{
int u = q.front(); q.pop(); x[u] = i;
for(int v : g[u])if(!--in[v])q.push(v);
}
for(int i = 1 ; i <= n ; i++)
g[i].clear() , in[i] = 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
cin >> a[i][j];
auto id = [&](int i , int j){return (i - 1) * n + j;};
auto merge = [&](int x , int y){fa[Find(x)] = Find(y);};
iota(fa + 1 , fa + n * n + 1 , 1);
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)if(j != i)
for(int k = 1 ; k <= n ; k++)if(k != i && k != j)
if(a[i][j] == a[i][k] && a[i][j] != a[j][k])
merge(id(i , j) , id(i , k)) , merge(id(j , i) , id(k , i));
for(int i = 1 ; i <= n ; i++)
for(int j = i + 1 ; j <= n ; j++)
if(Find(id(i , j)) == Find(id(j , i)))
for(int i = 1 ; i <= n ; i++)
for(int j = i + 1 ; j <= n ; j++)
{
int u = id(i , j) , v = id(j , i);
int fu = Find(u) , fv = Find(v);
if(fu == fv)return cout << "NO\n" , 0;
if(!vis[fu] && !vis[fv])vis[fu] = 1;
if(vis[fu])g[i].push_back(j) , in[j]++;
else g[j].push_back(i) , in[i]++;
}
BFS(x);
for(int i = 1 ; i <= n ; i++)
{
for(int j = i + 1 ; j <= n ; j++)
{
if((x[i] < x[j]) ^ a[i][j])g[j].push_back(i) , in[i]++;
else g[i].push_back(j) , in[j]++;
}
}
BFS(y);
cout << "YES\n";
for(int i = 1 ; i <= n ; i++)cout << x[i] << " \n"[i == n];
for(int i = 1 ; i <= n ; i++)cout << y[i] << " \n"[i == n];
return 0;
}
/*
4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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: 0ms
memory: 3552kb
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: 0ms
memory: 3548kb
input:
1 0
output:
YES 1 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 0 0 0 0
output:
YES 1 2 2 1
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 0 1 1 0
output:
YES 1 2 1 2
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 0 0 0 0 0 0 0 0 0
output:
YES 1 2 3 3 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 0 0 0 0 0 1 0 1 0
output:
YES 1 2 3 3 1 2
result:
ok ok
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
3 0 0 1 0 0 0 1 0 0
output:
YES 1 2 3 0 0 0
result:
wrong answer Integer parameter [name=q_0] equals to 0, violates the range [1, 3]