Submission #734929

#	Time	Username	Problem	Language	Result	Execution time	Memory
734929		tranxuanbach	Izlet (COI19_izlet)	C++17	100 / 100	655 ms	74816 KiB

izlet

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

template<bool Enable_small_to_large = true>
struct disjoint_set{
    int n, _classes;
    vector<int> p;
    disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
    int make_set(){
        p.push_back(-1);
        ++ _classes;
        return n ++;
    }
    int classes() const{
        return _classes;
    }
    int root(int u){
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b){
        return root(a) == root(b);
    }
    int size(int u){
        return -p[root(u)];
    }
    bool merge(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u;
        return true;
    }
    bool merge(int u, int v, auto act){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _classes;
        bool swapped = false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
        p[u] += p[v], p[v] = u;
        act(u, v, swapped);
        return true;
    }
    void clear(){
        _classes = n;
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up(){
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

const int N = 3e3 + 5;

int subtask;
int n;
int a[N][N];

disjoint_set dsu(N);
vi adj[N];

int col[N], cntcol;

int used[N];

int dfs_find_color(int u, int p, int orig, int cnt){
    if (~p){
        used[col[u]]++;
        if (used[col[u]] == 1){
            if (a[orig][u] == cnt){
                return col[u];
            }
            cnt++;
        }
    }
    Fora(v, adj[u]){
        if (v == p or col[v] == 0){
            continue;
        }
        int ans = dfs_find_color(v, u, orig, cnt);
        if (ans != 0){
            return ans;
        }
    }
    used[col[u]]--;
    return 0;
}

void dfs_color(int u, int p){
    if (~p){
        fill(used + 1, used + n + 1, 0);
        int ans = dfs_find_color(u, -1, u, 1);
        if (ans == 0){
            col[u] = ++cntcol;
        }
        else{
            col[u] = ans;
        }
    }
    Fora(v, adj[u]){
        if (v == p){
            continue;
        }
        dfs_color(v, u);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> subtask;
    cin >> n;
    For(u, 0, n){
        For(v, 0, n){
            cin >> a[u][v];
        }
    }

    For(u, 0, n){
        For(v, 0, n){
            if (a[u][v] == 1){
                dsu.merge(u, v, [&](int _u, int _v, bool _sw){
                    adj[u].emplace_back(v);
                    adj[v].emplace_back(u);
                });
            }
        }
    }
    For(u, 0, n){
        For(v, 0, n){
            if (a[u][v] == 2){
                dsu.merge(u, v, [&](int _u, int _v, bool _sw){
                    adj[u].emplace_back(v);
                    adj[v].emplace_back(u);
                });
            }
        }
    }

    col[0] = 1;
    cntcol = 1;
    dfs_color(0, -1);

    For(u, 0, n){
        cout << col[u] << ' ';
    } cout << endl;
    For(u, 0, n){
        Fora(v, adj[u]){
            if (u < v){
                cout << u + 1 << ' ' << v + 1 << endl;
            }
        }
    }
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

izlet.cpp:51:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   51 |     bool merge(int u, int v, auto act){
      |                              ^~~~

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