QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707986 | #9246. Dominating Point | cyc_43346# | WA | 1ms | 4048kb | C++14 | 2.8kb | 2024-11-03 18:41:22 | 2024-11-03 18:41:24 |
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;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= n ; j++)
{
char x;
scanf("%c" , &x);
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4048kb
input:
6 011010 000101 010111 100001 010100 100010
output:
1 2 3
result:
wrong answer Wrong Answer, Point not dominating.