QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#708013#9246. Dominating Pointcyc_43346#WA 1ms3864kbC++142.8kb2024-11-03 18:52:132024-11-03 18:52:14

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 18:38:25]
  • hack成功,自动添加数据
  • (/hack/1238)
  • [2024-11-03 18:52:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3864kb
  • [2024-11-03 18:52:13]
  • 提交

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.