QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628810#9246. Dominating PointyouthpaulTL 1ms3864kbC++201.6kb2024-10-10 22:27:432024-10-10 22:27:44

Judging History

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

  • [2024-11-22 18:38:25]
  • hack成功,自动添加数据
  • (/hack/1238)
  • [2024-10-10 22:27:44]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3864kb
  • [2024-10-10 22:27:43]
  • 提交

answer

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> d(n + 1, std::vector<int>(n + 1, INF));
    std::vector<std::vector<int>> g(n + 1);
    fore(i, 1, n + 1) d[i][i] = 0;
    fore(i, 1, n + 1){
        std::string s;
        std::cin >> s;
        s = '0' + s;
        fore(j, 1, n + 1)
            if(s[j] == '1'){
                g[i].push_back(j);
            }
    }

    auto bfs = [&](int s){
        std::queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto v : g[u])
                if(d[s][u] + 1 < d[s][v]){
                    d[s][v] = d[s][u] + 1;
                    if(d[s][v] != 2) q.push(v);
                }
        }
    };

    fore(i, 1, n + 1){
        bfs(i);
    }

    std::vector<int> ans;
    fore(u, 1, n + 1){
        int mx = 0;
        fore(v, 1, n + 1) mx = std::max(mx, d[u][v]);
        if(mx <= 2) ans.push_back(u);
        if(ans.size() == 3) break;
    }

    if(ans.size() < 3){
        std::cout << "NOT FOUND\n";
        return 0;
    }

    for(auto x : ans) std::cout << x << ' ';
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

6
011010
000101
010111
100001
010100
100010

output:

1 3 4 

result:

ok OK, Answer correct.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

3
011
001
000

output:

NOT FOUND

result:

ok OK, Answer correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

3
010
001
100

output:

1 2 3 

result:

ok OK, Answer correct.

Test #4:

score: -100
Time Limit Exceeded

input:

4994
0100001010011001010101110010101000111101111100100001110010000111100000000100110100101000001010100000010010010110110110111010010010100110100000110110111001010111010111010111011001000101001000010001010111110000000100001100000111100011001010010111011100111010101110011000010111101011111110001111110...

output:


result: