Submission #522235

#	Time	Username	Problem	Language	Result	Execution time	Memory
522235		blue	Kutije (COCI21_kutije)	C++17	70 / 70	175 ms	18284 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <string>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const int mx = 1'000;

vvi edge(1+mx);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;

    for(int j = 1; j <= m; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            int p;
            cin >> p;

            edge[p].push_back(i);
            edge[i].push_back(p);
        }
    }

    vi cc(1+n, 0);
    int cc_count = 0;

    for(int i = 1; i <= n; i++)
    {
        if(cc[i]) continue;
        cc_count++;

        cc[i] = cc_count;

        queue<int> tbv;
        tbv.push(i);
        while(!tbv.empty())
        {
            int u = tbv.front();
            tbv.pop();

            for(int v: edge[u])
            {
                if(cc[v]) continue;
                cc[v] = cc_count;
                tbv.push(v);
            }
        }
    }

    for(int x = 1; x <= q; x++)
    {
        int a, b;
        cin >> a >> b;

        if(cc[a] == cc[b]) cout << "DA\n";
        else cout << "NE\n";
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35