oj.uz

Submission #966799

# Submission time Handle Problem Language Result Execution time Memory
966799 2024-04-20T11:42:33 Z jcelin Izlet (COI19_izlet) C++14
100 / 100
 519 ms 74952 KB 
#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;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 381 ms 53588 KB Output is correct
3 Correct 368 ms 53584 KB Output is correct
4 Correct 341 ms 53608 KB Output is correct
5 Correct 365 ms 53432 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 53584 KB Output is correct
2 Correct 348 ms 53480 KB Output is correct
3 Correct 498 ms 74512 KB Output is correct
4 Correct 519 ms 74952 KB Output is correct
5 Correct 338 ms 53596 KB Output is correct
6 Correct 376 ms 60516 KB Output is correct
7 Correct 276 ms 50516 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 381 ms 53588 KB Output is correct
3 Correct 368 ms 53584 KB Output is correct
4 Correct 341 ms 53608 KB Output is correct
5 Correct 365 ms 53432 KB Output is correct
6 Correct 335 ms 53584 KB Output is correct
7 Correct 348 ms 53480 KB Output is correct
8 Correct 498 ms 74512 KB Output is correct
9 Correct 519 ms 74952 KB Output is correct
10 Correct 338 ms 53596 KB Output is correct
11 Correct 376 ms 60516 KB Output is correct
12 Correct 276 ms 50516 KB Output is correct
13 Correct 362 ms 54352 KB Output is correct
14 Correct 467 ms 61524 KB Output is correct
15 Correct 341 ms 53340 KB Output is correct
16 Correct 393 ms 58196 KB Output is correct
17 Correct 387 ms 59896 KB Output is correct
18 Correct 354 ms 53648 KB Output is correct
19 Correct 352 ms 53844 KB Output is correct
20 Correct 346 ms 53520 KB Output is correct
21 Correct 347 ms 54084 KB Output is correct
22 Correct 366 ms 53700 KB Output is correct
23 Correct 353 ms 54232 KB Output is correct
24 Correct 401 ms 60496 KB Output is correct
25 Correct 348 ms 53536 KB Output is correct