Submission #1139718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139718		roby	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	1 ms	2368 KiB

plaukimo_varzybos

#include <iostream>
#include <queue>
#include <vector>
#include <set>

using namespace std;

const int MAX = 2e4 + 7;
bool viz[MAX] = {0};
vector<int> vecini[MAX];
vector<int> bus[MAX];
set<int> s[MAX];
int cnt[MAX];
int k;

void bfs(int start)
{
    viz[start] = true;
    queue<int> q;
    q.push(start);
    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        for (auto x : vecini[curr])
        {
            if (!viz[x])
            {
                q.push(x);
                s[k].insert(x);
                viz[x] = true;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        char c;
        cin >> c;
        if (c == 'T')
        {
            vecini[a].push_back(b);
            vecini[b].push_back(a);
        }
        else
        {
            bus[a].push_back(b);
            bus[b].push_back(a);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!viz[i])
        {
            bfs(i);
            ++k;
        }
    }
    for (int i = 0; i < k; ++i)
    {
        if (!s[i].empty())
        {
            cnt[i] = s[i].size();
        }
    }
    int maxi = 0;
    int ans = 0;
    for (int i = 0; i < k; ++i)
    {
        if (cnt[i] > maxi)
        {
            maxi = cnt[0];
            ans = 1;
        }
        else if (cnt[i] == maxi)
        {
            ++ans;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (auto x : bus[i])
        {
            for (int j = 0; j < k; ++j)
            {
                if (s[i].find(x) != s[i].end())
                {
                    if (cnt[i] + cnt[j] > maxi)
                    {
                        maxi = cnt[i] + cnt[j];
                        ans = 1;
                    }
                    else if (cnt[i] + cnt[j] == maxi)
                    {
                        ++ans;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40