QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708013 | #9246. Dominating Point | cyc_43346# | WA | 1ms | 3864kb | C++14 | 2.8kb | 2024-11-03 18:52:13 | 2024-11-03 18:52:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int read()
{
int res = 0 , x = 1;
char ch = getchar();
while(ch > '9' || ch < '0')
{
if(ch == '-')
{
x = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res * x;
}
const int N = 5e3 + 9;
int n;
vector<int> node[N];
vector<int> node2[N];
int dfn[N] , low[N] , cnt , s[N] , st[N] , tp;
int scc[N] , sc , sz[N];
int in[N];
bool book[N];
void Tarjan(int now)
{
low[now] = dfn[now] = ++cnt;
s[++tp] = now;
st[now] = true;
for(auto to : node[now])
{
if(!dfn[to])
{
Tarjan(to);
low[now] = min(low[now] , low[to]);
}
else if(st[to])
{
low[now] = min(low[now] , dfn[to]);
}
}
if(dfn[now] == low[now])
{
sc++;
while(s[tp] != now)
{
scc[s[tp]] = sc;
sz[sc]++;
st[s[tp]] = false;
tp--;
}
scc[s[tp]] = sc;
sz[sc]++;
st[s[tp]] = false;
tp--;
}
}
void dfs(int now)
{
book[now] = true;
for(auto to : node2[now])
{
if(book[to])
{
continue;
}
dfs(to);
}
}
void solve()
{
cin >> n;
char x;
for(int i = 1 ; i <= n ; i++)
{
x = getchar();
for(int j = 1 ; j <= n ; j++)
{
x = getchar();
if(x == '1')
{
node[i].push_back(j);
}
}
}
for(int i = 1 ; i <= n ; i++)
{
if(!dfn[i])
{
Tarjan(i);
}
}
for(int i = 1 ; i <= n ; i++)
{
for(auto to : node[i])
{
if(scc[to] == scc[i])
{
continue;
}
in[scc[to]]++;
node2[scc[i]].push_back(scc[to]);
}
}
int tag = 0;
for(int i = 1 ; i <= sc ; i++)
{
if(!in[i])
{
if(tag)
{
cout << "NOT FOUND";
return;
}
tag = i;
}
}
if(sz[tag] < 3)
{
cout << "NOT FOUND";
return;
}
dfs(tag);
for(int i = 1 ; i <= sc ; i++)
{
if(!book[i])
{
cout << "NOT FOUND";
return;
}
}
int cnt = 0;
for(int i = 1 ; i <= n ; i++)
{
if(scc[i] == tag)
{
cout << i << " ";
cnt++;
if(cnt >= 3)
{
break;
}
}
}
}
int main()
{
solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3864kb
input:
6 011010 000101 010111 100001 010100 100010
output:
1 2 3
result:
wrong answer Wrong Answer, Point not dominating.