Submission #283676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283676	2020-08-26T05:20:28 Z	AMO5	Izlet (COI19_izlet)	C++17	100 / 100	814 ms	74744 KB

izlet

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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