Submission #485089

#TimeUsernameProblemLanguageResultExecution timeMemory
485089TrunktyIzlet (COI19_izlet)C++14
18 / 100
2101 ms368416 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); int n; vector<vector<int>> ans,ord; int arr[3005][3005]; int par[3005]; vector<int> roads[3005]; int col[3005]; vector<int> checked; int findpar(int x){ if(x!=par[x]){ int p = findpar(par[x]); par[x] = p; } return par[x]; } void domerge(int a, int b){ if(findpar(a)!=findpar(b)){ ans.push_back({a,b}); par[findpar(a)] = findpar(b); roads[a].push_back(b); roads[b].push_back(a); } } void dfs(int x, int par){ int iscol = x; for(int i:checked){ if(arr[x][i]==arr[par][i]){ iscol = col[i]; } } col[x] = iscol; checked.push_back(x); for(int i:roads[x]){ if(i!=par){ dfs(i,x); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int sub; cin >> sub; cin >> n; for(int i=1;i<=n;i++){ par[i] = i; for(int j=1;j<=n;j++){ cin >> arr[i][j]; if(i<j){ ord.push_back({arr[i][j],i,j}); } } } sort(ord.begin(),ord.end()); for(vector<int> i:ord){ domerge(i[1],i[2]); } dfs(1,0); for(int i=1;i<=n;i++){ cout << col[i] << " "; } cout << "\n"; for(vector<int> i:ans){ cout << i[0] << " " << i[1] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...