Submission #705171

#TimeUsernameProblemLanguageResultExecution timeMemory
705171NursikIzlet (COI19_izlet)C++14
100 / 100
648 ms61400 KiB
#include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <unordered_set> #include <unordered_map> #include <stdio.h> #include <bitset> #include <cstdint> #include <cassert> #include <functional> #include <complex> #include <random> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double const ll maxn = 3e3 + 10, maxm = 3e5 + 1; const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31; const ld eps = 1e-9; int s; int n, c; int p[maxn], sz[maxn], used[maxn], color[maxn]; int a[maxn][maxn]; vector<int> g[maxn]; int get(int v){ if (v == p[v]) return v; return p[v] = get(p[v]); } void unite(int a, int b){ int u = a, v = b; a = get(a), b = get(b); if (a == b) return; g[u].pb(v); g[v].pb(u); if (sz[a] > sz[b]) swap(a, b); sz[b] += sz[a]; p[a] = b; } int dfs2(int v, int p, int root, int cur = 1){ if (p){ used[color[v]] += 1; if (used[color[v]] == 1){ if (a[root][v] == cur){ return color[v]; } ++cur; } } for (auto to : g[v]){ if (color[to] > 0 && to != p){ int x = dfs2(to, v, root, cur); if (x > 0) return x; } } used[color[v]] -= 1; return 0; } void dfs(int v = 1, int p = 0){ if (p){ color[v] = dfs2(v, 0, v); if (color[v] == 0){ color[v] = ++c; } for (int j = 1; j <= n; ++j){ used[j] = 0; } } for (auto to : g[v]){ if (to != p){ dfs(to, v); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> s; cin >> n; for (int i = 1; i <= n; ++i){ p[i] = i, sz[i] = 1; } for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j){ cin >> a[i][j]; if (a[i][j] == 1){ unite(i, j); } } } vector<int> roots; for (int i = 1; i <= n; ++i){ int x = get(i); if (used[x] == 0){ roots.pb(x); } } for (int i = 0; i < (int)roots.size(); ++i){ int x = roots[i]; for (int j = i + 1; j < (int)roots.size(); ++j){ int y = roots[j]; if (a[x][y] == 2){ unite(x, y); } } } color[1] = 1; c = 1; dfs(); for (int i = 1; i <= n; ++i){ cout << color[i] << " "; } cout << '\n'; for (int i = 1; i <= n; ++i){ for (auto it : g[i]){ if (i < it){ cout << i << " " << it << '\n'; } } } } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...