Submission #781042

#	Time	Username	Problem	Language	Result	Execution time	Memory
781042		cig32	Kutije (COCI21_kutije)	C++17	70 / 70	147 ms	26052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;

    vector<int> adj[MAXN], adj2[MAXN], adj3[MAXN];
bool vis[MAXN];
stack<int> topolo;
void dfs1(int node) {
    vis[node] = 1;
    for(int x: adj[node]) {
        if(!vis[x]) dfs1(x);
    }
    topolo.push(node);
}
vector<vector<int> > components;
vector<int> wow;
void dfs2(int node) {
    vis[node] = 1;
    for(int x : adj2[node]) {
        if(!vis[x]) dfs2(x);
    }
    wow.push_back(node);
}
void dfs3(int node) {
    vis[node] = 1;
    for(int x : adj3[node]) {
        if(!vis[x]) dfs3(x);
    }
    topolo.push(node);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    int ans[n+1][n+1];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            ans[i][j] = 0;
        }
    }
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            int x; cin >> x;
            adj[x].push_back(j);
            adj2[j].push_back(x);
        }
    }
    for(int i=1; i<=n; i++) {
        if(!vis[i]) {
            dfs1(i);
        }
    }
    for(int i=1; i<=n; i++) {
        vis[i] = 0;
    }
    int dage[n+1];
    while(topolo.size()) {
        if(!vis[topolo.top()]){
            vis[topolo.top()]=1;
            wow.clear();
            dfs2(topolo.top());
            for(int x : wow) {
                for(int y : wow) {
                    ans[x][y] = 1;
                }
            }
            for(int x : wow) {
                dage[x] = wow[0];
            }
            components.push_back(wow);
        }
        topolo.pop();
    }
    int done[n+1][n+1];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            done[i][j] = 0;
        }
    }
    for(int i=1; i<=n; i++) {
        for(int x : adj[i]) {
            if(dage[i] != dage[x] && done[dage[i]][dage[x]] == 0) {
                adj3[dage[i]].push_back(dage[x]);
                done[dage[i]][dage[x]] = 1;
            } 
        }
    }
    while(q--) {
        int a, b; cin >> a >> b;
        cout << (ans[a][b]? "DA\n":"NE\n");
    }
}

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