Submission #1041521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041521		vjudge1	Izlet (COI19_izlet)	C++17	18 / 100	301 ms	71312 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
const ll N = 3010;
int parent[N];
ll get_parent(ll u){
  return ((u!=parent[u]) ? parent[u]=get_parent(parent[u]) : u);
}
void solve(){
    ll n;
    cin >> n;
    for(int i =1; i<= n ;i ++){
        parent[i] = i;
    }
    vector<vector<ll>> mtx(n + 1, vector<ll> (n + 1));
    for(int i = 1; i<= n ; i++){
        for(int j = 1; j<= n ;j ++){
            cin >> mtx[i][j];
            if(i == j){
                continue;
            }
            ll  x = get_parent(i) , y = get_parent(j);
            if(mtx[i][j] == 1 and x != y){
                parent[x] = y;
            }
        }
    }
    map<ll,vector<ll>> mp;
    for(int i =1; i <= n; i ++){
        ll x = get_parent(i);
        cout << 1 + (x != get_parent(1)) << " "; 
        if(i != 1){
            mp[x].push_back(i);
        }
    }
    cout << '\n';
    for(auto i : mp){
        ll x = 1;
        for(auto j : i.second){
            cout << x << " "<<j << '\n';
            x = j;
        }
    }
    cout << '\n';

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tests = 1;
    cin >> tests;
    if(tests == 1){
        for (int i = 1; i <= tests; i++){
            solve();
        }
    }
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57