Submission #331781

#	Time	Username	Problem	Language	Result	Execution time	Memory
331781		thecodingwizard	Izlet (COI19_izlet)	C++11	100 / 100	1744 ms	84600 KiB

izlet

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 3000
int n; 
int input[maxn][maxn];

vector<int> nodes; // stores nodes remaining after 1's are compressed
map<int, vector<int>> nodesInOneComponent;
void compressOnes() {
    vector<bool> done(n, 0);
    F0R(i, n) {
        if (done[i]) continue;
        nodes.pb(i);
        done[i] = true;
        F0R(j, n) {
            if (input[i][j] == 1 && j != i) {
                nodesInOneComponent[i].pb(j);
                done[j] = true;
            }
        }
    }
}

vector<vector<int>> twoComponents;
bool inSameComponent[maxn][maxn];
vector<int> components[maxn];
void findTwos() {
    for (int n1 : nodes) {
        for (int n2 : nodes) {
            if (inSameComponent[n1][n2]) continue;
            if (input[n1][n2] != 2) continue;

            twoComponents.pb(vector<int>());
            twoComponents.back().pb(n1);
            twoComponents.back().pb(n2);
            for (int n3 : nodes) {
                if (input[n1][n3] == 2 && input[n2][n3] == 2) {
                    twoComponents.back().pb(n3);
                }
            }

            for (int x : twoComponents.back()) {
                for (int y : twoComponents.back()) {
                    inSameComponent[x][y] = 1;
                }
                components[x].pb(twoComponents.size()-1);
            }
        }
    }

    /*
    for (auto x : twoComponents) {
        for (auto y : x) {
            cout << y << " ";
        }
        cout << endl;
    }
    cout << "---" << endl;
    */
}

int assignedColor[maxn];
vector<ii> outputEdges;
vector<int> adj[maxn];
bool inQueue[maxn];

map<int, int> colors;
int target = -1;
int findColor(int u, int p) {
    if ((int)colors.size() == input[target][u]) {
        return assignedColor[u];
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        colors[assignedColor[v]]++;

        int r = findColor(v, u);

        colors[assignedColor[v]]--;
        if (colors[assignedColor[v]] == 0) {
            colors.erase(assignedColor[v]);
        }
        if (r != 0) return r;
    }
    return 0;
}

void buildTree() {
    int colors = 2;
    assignedColor[nodes[0]] = 1;
    queue<int> q;
    for (int c : components[nodes[0]]) {
        q.push(c);
        inQueue[c] = true;
    }

    while (!q.empty()) {
        int c = q.front(); q.pop();
        int rootNode = -1;
        int childNode = -1;
        for (int x : twoComponents[c]) {
            if (assignedColor[x] > 0) {
                assert(rootNode == -1);
                rootNode = x;
            } else {
                childNode = x;
            }
        }

        adj[childNode].pb(rootNode);
        adj[rootNode].pb(childNode);
        outputEdges.pb(mp(childNode, rootNode));

        target = childNode;
        assignedColor[childNode] = findColor(childNode, childNode);
        if (assignedColor[childNode] == 0) {
            assignedColor[childNode] = colors++;
        }

        for (int x : twoComponents[c]) {
            if (x != rootNode && x != childNode) {
                assignedColor[x] = assignedColor[childNode];
                adj[x].pb(rootNode);
                adj[rootNode].pb(x);
                outputEdges.pb(mp(x, rootNode));
            }
            for (int c : components[x]) {
                if (!inQueue[c]) {
                    q.push(c);
                    inQueue[c] = true;
                }
            }
        }
    }
}

void decompressOnes() {
    for (int x : nodes) {
        for (int y : nodesInOneComponent[x]) {
            outputEdges.pb(mp(x, y));
            assignedColor[y] = assignedColor[x];
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int subtask; cin >> subtask;
    cin >> n;
    F0R(i, n) {
        F0R(j, n) {
            cin >> input[i][j];
        }
    }

    compressOnes();

    findTwos();

    buildTree();

    decompressOnes();

    F0R(i, n) cout << assignedColor[i] << " ";
    cout << endl;
    for (auto x : outputEdges) cout << x.f+1 << " " << x.s+1 << endl;
    assert((int)outputEdges.size()==n-1);
    F0R(i, n) assert(assignedColor[i]>0);

    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57