Submission #639178

#	Time	Username	Problem	Language	Result	Execution time	Memory
639178		delrey	Kutije (COCI21_kutije)	C++14	70 / 70	960 ms	13376 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n, m, q;
int p[1000][1000];
int u[1000], s[1000];
bool vis[1000];

int Root(int x)
{
    while(x != u[x])
        x = u[x];
    return x;
}

void Unite(int x, int y)
{
    x = Root(x);
    y = Root(y);
    if(x == y)
        return;
    if(s[x] > s[y])
        swap(x, y);
    u[x] = y;
    s[y] += s[x];
}

int main()
{
    cin>>n>>m>>q;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
        {
            cin>>p[i][j];
            p[i][j]--;
        }
    for(int i = 0; i < n; i++)
    {
        u[i] = i;
        s[i] = 1;
    }
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
            vis[j] = false;
        for(int j = 0; j < n; j++)
        {
            if(vis[j])
                continue;
            vis[j] = true;
            int x = p[i][j];
            while(x != j)
            {
                vis[x] = true;
                Unite(x, j);
                x = p[i][x];
            }
        }
    }
    //for(int i = 0; i < n; i++)
    //    cout<<u[i]<<" ";
    //cout<<endl;
    for(int i = 0; i < q; i++)
    {
        int x, y;
        cin>>x>>y;
        x--;
        y--;
        if(Root(x) == Root(y))
            cout<<"DA"<<endl;
        else
            cout<<"NE"<<endl;
    }
    return 0;
}

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