QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708039 | #9246. Dominating Point | cyc_43346# | WA | 1ms | 3860kb | C++14 | 2.8kb | 2024-11-03 19:01:27 | 2024-11-03 19:01:33 |
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] , dfncnt , s[N] , in_stack[N] , tp;
int scc[N] , sc , sz[N];
int in[N];
bool book[N];
void Tarjan(int u)
{
low[u] = dfn[u] = ++dfncnt;
s[++tp] = u;
in_stack[u] = true;
for(auto v : node[u])
{
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u] , low[v]);
}
else if(in_stack[v])
{
low[u] = min(low[u] , dfn[v]);
}
}
if(dfn[u] == low[u])
{
sc++;
while(s[tp] != u)
{
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = false;
tp--;
}
scc[s[tp]] = sc;
sz[sc]++;
in_stack[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++)
{
for(int j = 1 ; j <= n ; j++)
{
cin >> 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: 3860kb
input:
6 011010 000101 010111 100001 010100 100010
output:
1 2 3
result:
wrong answer Wrong Answer, Point not dominating.