oj.uz

답안 #234738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234738 2020-05-25T12:19:34 Z amoo_safar Izlet (COI19_izlet) C++14
100 / 100
 718 ms 53856 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 3e3 + 10;
const ll Inf = 1e9;
const ll Log = 30;

int n;
int sm[N], mk[N], dis[N][N], c[N];
vector<int> G[N];
vector<pll> E;

void Mark(int u){
	mk[u] = 1;
	for(int v = 1; v <= n; v++) if(!mk[v]) sm[v] += dis[u][v];
}

int sc, st;
void DFS(int u, int p){
	if(dis[sc][u] == dis[st][u]){
		c[sc] = c[u];
		return ;
	}
	for(auto adj : G[u]) if(adj != p) DFS(adj, u);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	//assert(T == 1);
	cin >> n;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> dis[i][j];
	
	sm[n + 1] = Inf;
	int mn;
	Mark(1); c[1] = 1;
	for(int it = 2; it <= n; it++){
		mn = n + 1;
		for(int i = 1; i <= n; i++) if(!mk[i] && sm[i] < sm[mn]) mn = i;
		for(int i = 1; i <= n; i++){
			if(dis[mn][i] == 1 && mk[i] == 1){
				c[mn] = c[i];
				E.pb({mn, i});
				G[mn].pb(i);
				G[i].pb(mn);
				Mark(mn);
				break;
			}
		}
		if(mk[mn]) continue;
		int u = -1;
		for(int i = 1; i <= n; i++) if(mk[i] == 1 && dis[mn][i] == 2) u = i;
		assert(u > 0);
		Mark(mn);
		c[mn] = it;
		E.pb({mn, u});
		G[mn].pb(u);
		G[u].pb(mn);

		sc = mn;
		st = u;
		DFS(st, sc);
	}
	//cerr << '\n';

	for(int i = 1; i <= n; i++) cout << c[i] << ' ';
	cout << '\n';
	for(auto x : E) cout << x.F << ' ' << x.S << '\n';
	return 0;
}

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 601 ms 53580 KB Output is correct
3 Correct 565 ms 53652 KB Output is correct
4 Correct 535 ms 36984 KB Output is correct
5 Correct 550 ms 36472 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 626 ms 37544 KB Output is correct
2 Correct 516 ms 36676 KB Output is correct
3 Correct 713 ms 52600 KB Output is correct
4 Correct 718 ms 40824 KB Output is correct
5 Correct 510 ms 53624 KB Output is correct
6 Correct 576 ms 38264 KB Output is correct
7 Correct 437 ms 33016 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 601 ms 53580 KB Output is correct
3 Correct 565 ms 53652 KB Output is correct
4 Correct 535 ms 36984 KB Output is correct
5 Correct 550 ms 36472 KB Output is correct
6 Correct 626 ms 37544 KB Output is correct
7 Correct 516 ms 36676 KB Output is correct
8 Correct 713 ms 52600 KB Output is correct
9 Correct 718 ms 40824 KB Output is correct
10 Correct 510 ms 53624 KB Output is correct
11 Correct 576 ms 38264 KB Output is correct
12 Correct 437 ms 33016 KB Output is correct
13 Correct 655 ms 42820 KB Output is correct
14 Correct 681 ms 38136 KB Output is correct
15 Correct 538 ms 53624 KB Output is correct
16 Correct 615 ms 38264 KB Output is correct
17 Correct 653 ms 38140 KB Output is correct
18 Correct 574 ms 51960 KB Output is correct
19 Correct 617 ms 52088 KB Output is correct
20 Correct 541 ms 51960 KB Output is correct
21 Correct 595 ms 42616 KB Output is correct
22 Correct 610 ms 53744 KB Output is correct
23 Correct 599 ms 38076 KB Output is correct
24 Correct 656 ms 38136 KB Output is correct
25 Correct 581 ms 53856 KB Output is correct