编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#5977 #1006. mygo图 Accepted 100 571 ms 9060 K C++ 17 / 2.5 K C192022211986 2023-09-25 12:08:21
显示原始代码
#include <bits/stdc++.h>

using namespace std;

#define fi first

#define sc second

#define endl '\n'

#define pb push_back

#define mem0(a) memset(a, 0, sizeof(a))

#define mem1(a) memset(a, -1, sizeof(a))

#define meminf(a) memset(a, 0x3f, sizeof(a))

#define debug(x) cout << "----Line#" << x << "----" << endl


typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
typedef pair<char, char> PCC;
typedef pair<int, string> PIS;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = 1e9 + 7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int N = 4010;
int n, m;
int id[N];
vector<int> g[N];
int cn;
vector<int> scc[N];
int edge_num[N];
string s[N];
string t[N];

void dfs(int nw) {
    id[nw] = cn;
    scc[cn].pb(nw);
    for (int i = 0; i < g[nw].size(); i++) {
        int to = g[nw][i];
        if (!id[to])
            dfs(to);
    }
    return;
}

void solve() {
    cin >> n >> m;
    cn = 0;
    int all_num = 0;
    mem0(id);
    mem0(g);
    mem0(scc);
    mem0(edge_num);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = ' ' + s[i];
        for (int j = 1; j <= n; j++) {
            if (s[i][j] == '1') {
                g[i].pb(j);
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        cin >> t[i];
        t[i] = ' ' + t[i];
        for (int j = 1; j <= m; j++) {
            if (t[i][j] == '1') {
                g[i + n].pb(j + n);
            }
        }
    }

    for (int i = 1; i <= n + m; i++) {
        if (!id[i])
            ++cn, dfs(i);
    }

    bool fl = false;
    for (int i = 1; i <= 2; i++) {
        for (int j = 0; j < scc[i].size(); j++) {
            for (int k = j + 1; k < scc[i].size(); k++) {
                for (auto x : g[scc[i][j]]) {
                    if (x == scc[i][k])
                        edge_num[i]++;
                }
            }
        }

        if (edge_num[i] == scc[i].size() * (scc[i].size() - 1) / 2) {
            all_num++;
            if (i == 1)
                fl = true;
        }
    }
    if (all_num == 2) {
        cout << n << endl;
    } else if (all_num == 1) {
        if (fl) {
            cout << 2 << endl;
        } else {
            cout << 1 << endl;
        }
    } else {
        cout << 1 << endl;
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:4 ms
内存:832 KiB

输入文件(1.in

10 100
0110110001
1101000100
1000010000
0100101101
1001011001
1010101000
0001110011
01010000
<10226 bytes omitted>

答案文件(1.out

1

用户输出

1

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:82 ms
内存:9060 KiB

输入文件(2.in

2000 2000
01000100000000000000000000000100000000100000000000000000000000000000000000000000000001000
<8007911 bytes omitted>

答案文件(2.out

1

用户输出

1

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:840 KiB

输入文件(3.in

30 40
011111111111111111111111111111
101111111111111111111111111111
11011111111111111111111111111
<2547 bytes omitted>

答案文件(3.out

30

用户输出

30

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:481 ms
内存:7544 KiB

输入文件(4.in

1000 1000
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
<2003911 bytes omitted>

答案文件(4.out

2

用户输出

2

系统信息

Exited with return code 0