Submission #1280124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280124		edo	Izlet (COI19_izlet)	C++20	0 / 100	293 ms	58068 KiB

izlet

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

class DSU{
    int n;
    vector<int> parent, sz;
    
public:
    DSU(int _n):n(_n), parent(_n), sz(_n, 1){
        iota(parent.begin(), parent.end(), 0);
    }

    void reset(){
        iota(parent.begin(), parent.end(), 0);
        fill(sz.begin(), sz.end(), 1);
    }

    int find(int x){
        if(x!=parent[x]){
            parent[x]=find(parent[x]);
        }       
        return parent[x];
    }

    bool unite(int x, int y){
        x=find(x);
        y=find(y);
        if(x==y)return false;
        if(sz[x]<sz[y])swap(x, y);
        parent[y]=x;
        sz[x]+=sz[y];
        return true;
    }

    bool same(int x, int y){
        return find(x)==find(y);
    }

    int size(int x){
        return sz[find(x)];
    }
};

void solve() {
    int _;
    cin >> _;
    int n;
    cin >> n;

    vector<vector<int>> g(n, vector<int>(n, 0));

    DSU dsu(n);
    for(int i=0; i<n; i++) 
        for(int j=0; j<n; j++){
            cin >> g[i][j];
            if(g[i][j]==1) dsu.unite(i, j);
        }
           
    vector<int> id(n, -1);
    vector<vector<int>> comp;
    for(int i=0; i<n; i++) {
        int r = dsu.find(i);
        if(id[r]==-1) {
            id[r] = (int)comp.size();
            comp.push_back({});
        }
        comp[id[r]].push_back(i);
    }
    
    vector<int> root(n, -1);
    int idx = 0;
    for(int i=0; i<n; i++)
        if(dsu.find(i)==i) 
            if(root[i]==-1) 
                root[i] = idx++;

    vector<int> rep(n, -1);
    for(int i=0; i<n; i++) rep[i] = dsu.find(i);

    unordered_map<int, int> mp;
    mp.reserve(n<<1);
    comp.clear();

    for(int i=0; i<n; i++){
        int rroot = rep[i];
        if(mp.find(rroot)==mp.end()) {
            int idd = (int)comp.size();
            mp[rroot]=idd;
            comp.push_back({});
        } 
        comp[mp[rroot]].push_back(i);
    }

    int m = (int)comp.size();
    for(int i=0; i<m; i++) rep[i] = comp[i][0];

    if(m==1) {
        for(int i=0; i<n; i++) {
            if(i) cout << " ";
            cout << 1;
        }
        cout << "\n";
        for(int i=1; i<n; i++) {
            cout << i << " " << i+1 << "\n";
        }
        return;
    }
    const int INF = (int)1e9;
    vector d(m, vector<int>(m, INF));
    for(int i=0; i<m; i++) 
        for(int j=0; j<m; j++) 
            d[i][j] = g[rep[i]][rep[j]] - 1;
        
    int r = 0;
    vector<int> droot(m, INF);
    int mx = 0;
    for(int i=0; i<m; i++) {
        droot[i] = d[r][i];
        if(droot[i] < INF) mx = max(mx, droot[i]);
    }

    vector<vector<int>> buckets(mx+1);
    for(int i=0; i<m; i++) 
        if(droot[i] < INF) buckets[droot[i]].push_back(i);
    vector<vector<int>> nodes(mx+1);
    vector<char> added(m, 0);
    added[r] = 1;
    nodes[0].push_back(r);
    vector<pair<int, int>> edges;
    for(int dd=1; dd<mx+1; dd++) {
        for(int cur : buckets[dd]) {
            int p = -1;
            for(int cand : nodes[dd-1]) {
                if(d[cand][cur] == 1) {
                    p = cand;
                    break;
                }
            }
            if(p==-1) {
                for(int pd=dd-1; ~pd && p==-1; --pd) {
                    for(int cand : nodes[pd]) {
                        if(d[cand][cur] == 1) {
                            p = cand;
                            break;
                        }
                    }
                }
            }
            edges.emplace_back(p, cur);
            added[cur] = 1;
            nodes[dd].push_back(cur);
        }
    }

    vector<pair<int, int>> fedges;
    for(int i=0; i<m; i++) {
        int rn = rep[i];
        for(size_t k=1; k<ssize(comp[i]); ++k) {
            fedges.emplace_back(rn+1, comp[i][k]+1);
        }
    }

    for(auto &[u, v] : edges) {
        fedges.emplace_back(u+1, v+1);
    }

    vector<int> c(n);
    for(int i=0; i<m; i++) {
        for(auto &j : comp[i])
            c[j] = i+1;
    }
    for(int i=0; i<n; i++) {
        if(i) cout << " ";
        cout << c[i];
    }
    cout << "\n";
    for(auto &[u, v] : fedges) {
        cout << u << " " << v << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

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