QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628798#9246. Dominating PointyouthpaulTL 0ms3616kbC++201.4kb2024-10-10 22:19:052024-10-10 22:19:10

Judging History

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

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

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));
    fore(i, 1, n + 1) d[i][i] = 0;
    std::vector<std::pair<int, int>> e;
    fore(i, 1, n + 1){
        std::string s;
        std::cin >> s;
        s = '0' + s;
        fore(j, 1, n + 1)
            if(s[j] == '1')
                e.push_back({i, j});
    }

    for(auto [u, v] : e) d[u][v] = 1;
    fore(i, 0, e.size()){
        auto [u, v] = e[i];
        fore(j, 0, e.size()){
            auto [x, y] = e[j];
            if(v != x) continue;
            d[u][y] = std::min(d[u][y], 2);
        }
    }


    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: 0ms
memory: 3616kb

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: 3500kb

input:

3
011
001
000

output:

NOT FOUND

result:

ok OK, Answer correct.

Test #3:

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

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: