Submission #966799

#TimeUsernameProblemLanguageResultExecution timeMemory
966799jcelinIzlet (COI19_izlet)C++14
100 / 100
519 ms74952 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<pll> vpll; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; //998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int MAXN = 3e3 + 7; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int mat[MAXN][MAXN], pred[MAXN], col[MAXN], bio[MAXN], nod = 1; vi g[MAXN], pop; struct uf{ int par[MAXN], sz[MAXN]; uf(){ for(int i=1; i<MAXN; i++) par[i] = i, sz[i] = 1; } int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); } bool same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ if(same(a, b)) return; g[a].PB(b); g[b].PB(a); a = find(a), b = find(b); if(sz[a] < sz[b]) swap(a, b); par[b] = a; } }t; int nadi_boju(int u, int cr, int p = -1){ if(p != -1 and col[u] and !bio[col[u]]){ if(mat[cr][u] == mat[cr][p]) return col[u]; } bio[col[u]]++; for(auto &x : g[u]){ if(x == p) continue; int vl = nadi_boju(x, cr, u); if(vl) return vl; } bio[col[u]]--; return 0; } void dfs(int u, int p = -1){ fill(bio, bio + MAXN, 0); col[u] = nadi_boju(u, u, -1); if(col[u] == 0) col[u] = nod++; for(auto &x : g[u]) if(x != p) dfs(x, u); } void solve(){ int n; cin >> n; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) cin >> mat[i][j]; } for(int i=1; i<=n; i++){ if(pred[i]) continue; for(int j=1; j<=n; j++) if(mat[i][j] == 1) pred[j] = i; pop.PB(i); } for(auto &x : pop) for(auto &y : pop) if(mat[x][y] == 2) t.unite(x, y); dfs(1); for(int i=1; i<=n; i++) cout << col[pred[i]] << " "; cout << "\n"; for(int i=1; i<=n; i++){ for(auto &x : g[i]) if(i < x) cout << i << " " << x << "\n"; if(pred[i] != i) cout << pred[i] << " " << i << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int _; cin >> _; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...