oj.uz

답안 #734929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734929 2023-05-03T09:29:19 Z tranxuanbach Izlet (COI19_izlet) C++17
100 / 100
 655 ms 74816 KB 
#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

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.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 459 ms 53408 KB Output is correct
3 Correct 464 ms 53444 KB Output is correct
4 Correct 476 ms 53280 KB Output is correct
5 Correct 471 ms 53200 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 35900 KB Output is correct
2 Correct 476 ms 53364 KB Output is correct
3 Correct 623 ms 74040 KB Output is correct
4 Correct 655 ms 74816 KB Output is correct
5 Correct 441 ms 53340 KB Output is correct
6 Correct 493 ms 60384 KB Output is correct
7 Correct 367 ms 49316 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 459 ms 53408 KB Output is correct
3 Correct 464 ms 53444 KB Output is correct
4 Correct 476 ms 53280 KB Output is correct
5 Correct 471 ms 53200 KB Output is correct
6 Correct 448 ms 35900 KB Output is correct
7 Correct 476 ms 53364 KB Output is correct
8 Correct 623 ms 74040 KB Output is correct
9 Correct 655 ms 74816 KB Output is correct
10 Correct 441 ms 53340 KB Output is correct
11 Correct 493 ms 60384 KB Output is correct
12 Correct 367 ms 49316 KB Output is correct
13 Correct 479 ms 54396 KB Output is correct
14 Correct 609 ms 61396 KB Output is correct
15 Correct 473 ms 53340 KB Output is correct
16 Correct 536 ms 57912 KB Output is correct
17 Correct 521 ms 59768 KB Output is correct
18 Correct 464 ms 53424 KB Output is correct
19 Correct 506 ms 53328 KB Output is correct
20 Correct 473 ms 53480 KB Output is correct
21 Correct 488 ms 54220 KB Output is correct
22 Correct 506 ms 53628 KB Output is correct
23 Correct 478 ms 54220 KB Output is correct
24 Correct 533 ms 60516 KB Output is correct
25 Correct 467 ms 53688 KB Output is correct