Submission #1341134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341134		hauserl	KOVANICE (COI15_kovanice)	C++20	50 / 100	2097 ms	28716 KiB

kovanice

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Node {
    vector<int> parents; // Item pos
    vector<int> children;
    Node* root = nullptr;
    int depth = -1;
    bool isValid = false;
};

struct Item {
    Node* node = nullptr;
    int coinNum = -1;
};


int N,M,V; 
vector<Item> items;
vector<int> dsu;
vector<int> dsuSize;



int dfs(Node* node, int depth) {
    node->depth = depth;
    int maxD = depth;
    for (const auto& child : node->children) {
        maxD = max(maxD, dfs(items[child].node, depth+1));
    }
    return maxD;
}

void dfs2(Node* node) {
    node->isValid = true;
    for (const auto& child : node->children) {
        dfs2(items[child].node);
    }
}


int findR(int a) {
    int p = dsu[a];
    if (p != -1) return dsu[a] = findR(p);
    return a;
}

void unionR(int a, int b) {
    a = findR(a); b = findR(b);
    if (a == b) return;
    if (dsuSize[a] < dsuSize[b]) swap(a, b);
    dsu[a] = b;
    dsuSize[a] += dsuSize[b];
}

int main() {

    scanf("%d %d %d",&N,&M,&V);

    items.resize(M, Item{nullptr, -1});

    vector<pair<int, int>> equal;
    vector<pair<int, int>> less;

    for (int i = 0; i < V; i++) {
        int A,B; char C; scanf("%d %c %d", &A, &C,&B);
        A--;
        B--;

        if (C == '=') {
            equal.push_back({A,B});
        } else { // A < B
            less.push_back({A,B});
        }
    }

    // DSU for equality than less

    dsu.resize(M, -1); 
    dsuSize.resize(M, 1); 

    for (int i = 0; i < equal.size(); i++) {
        auto e = equal[i];
        unionR(e.first, e.second);
    }



    for (int i = 0; i < less.size(); i++) {
        auto l = less[i];
        int p = findR(l.first);
        int c = findR(l.second);
        if (!items[c].node) items[c].node = new Node{{}, {}, nullptr, -1, false};
        if (!items[p].node) items[p].node = new Node{{}, {}, nullptr, -1, false};
        items[c].node->parents.push_back(p);
        items[p].node->children.push_back(c);
    }

    for (int i = 0; i < items.size(); i++) {
        if (items[i].node && items[i].node->depth == -1 && items[i].node->parents.empty()) {
            int maxD = dfs(items[i].node, 1);

            if (maxD == N) {
                dfs2(items[i].node);
            }
        }   
    }


    for (int i = 0; i < items.size(); i++) {
        int coinNum = -1;
        int r = findR(i);
        if (items[r].node && items[r].node->isValid) coinNum = items[r].node->depth;

        if (coinNum == -1) printf("?\n");
        else printf("K%d\n", coinNum);
    }

    return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'int main()':
kovanice.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d %d",&N,&M,&V);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
kovanice.cpp:67:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         int A,B; char C; scanf("%d %c %d", &A, &C,&B);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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