oj.uz

답안 #283676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283676 2020-08-26T05:20:28 Z AMO5 Izlet (COI19_izlet) C++17
100 / 100
 814 ms 74744 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=3e3+5;
bool DEBUG=0;

int a[mxn][mxn],n,subt;
int col[mxn];
bool vis[mxn];
vector<ii>edges;
vi adj[mxn];

struct DSU{
	vi par;
	DSU(int n){
		for(int i=0; i<=n; i++)par.eb(i);
	}
	void reset(int n){
		par=vi();
		for(int i=0; i<=n; i++)par.eb(i);
	}
	int rt(int u){
		if(u!=par[u])par[u]=rt(par[u]);
		return par[u];
	}
	void merge(int u, int v){
		u=rt(u); v=rt(v);
		if(u==v)return;
		par[v]=u;
	}
	bool sameset(int u, int v){
		return ((u=rt(u))==(v=rt(v)));
	}
};

DSU dsu(1);

void dfs(int pr, int st, int u, int p){
	if(a[pr][u]==a[st][u]){
		//cerr<<pr<<" "<<st<<" "<<u<<" "<<p<<" : "<<a[st][u]<<"\n";
		dsu.merge(pr,u);
		return;
	}
	for(int v:adj[u]){
		if(v==p)continue;
		dfs(pr,st,v,u);
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    cin>>subt>>n;
    dsu.reset(n);
    for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin>>a[i][j];
			if(i>j&&a[i][j]==1){
				if(dsu.sameset(i,j))continue;
				edges.eb(j,i);
				adj[i].eb(j);
				adj[j].eb(i);
				dsu.merge(i,j);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i>j&&a[i][j]==2){
				if(dsu.sameset(i,j))continue;
				edges.eb(j,i);
				adj[i].eb(j);
				adj[j].eb(i);
				dsu.merge(i,j);
			}
		}
	}
	dsu.reset(n);
	for(int i=1; i<=n; i++){
		for(int j:adj[i]){
			dfs(i,j,j,i);
		}
	}
	for(int i=1; i<=n; i++)cout<<dsu.rt(i)<<" ";
	cout<<"\n";
	for(int i=0; i<sz(edges); i++){
		cout<<edges[i].fi<<" "<<edges[i].se<<"\n";
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 723 ms 35960 KB Output is correct
3 Correct 679 ms 36088 KB Output is correct
4 Correct 641 ms 35960 KB Output is correct
5 Correct 676 ms 36000 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 35848 KB Output is correct
2 Correct 664 ms 53572 KB Output is correct
3 Correct 791 ms 74168 KB Output is correct
4 Correct 814 ms 74744 KB Output is correct
5 Correct 603 ms 53628 KB Output is correct
6 Correct 654 ms 60536 KB Output is correct
7 Correct 478 ms 49348 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 723 ms 35960 KB Output is correct
3 Correct 679 ms 36088 KB Output is correct
4 Correct 641 ms 35960 KB Output is correct
5 Correct 676 ms 36000 KB Output is correct
6 Correct 616 ms 35848 KB Output is correct
7 Correct 664 ms 53572 KB Output is correct
8 Correct 791 ms 74168 KB Output is correct
9 Correct 814 ms 74744 KB Output is correct
10 Correct 603 ms 53628 KB Output is correct
11 Correct 654 ms 60536 KB Output is correct
12 Correct 478 ms 49348 KB Output is correct
13 Correct 678 ms 54580 KB Output is correct
14 Correct 794 ms 61408 KB Output is correct
15 Correct 621 ms 53540 KB Output is correct
16 Correct 664 ms 57976 KB Output is correct
17 Correct 694 ms 59892 KB Output is correct
18 Correct 614 ms 53584 KB Output is correct
19 Correct 685 ms 53672 KB Output is correct
20 Correct 646 ms 53624 KB Output is correct
21 Correct 688 ms 54136 KB Output is correct
22 Correct 674 ms 53788 KB Output is correct
23 Correct 705 ms 54548 KB Output is correct
24 Correct 676 ms 60792 KB Output is correct
25 Correct 641 ms 53624 KB Output is correct