Submission #1041723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041723		vjudge1	Izlet (COI19_izlet)	C++17	43 / 100	409 ms	91088 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
int tests = 1;
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;
            }
        }
    }
    if(tests == 1){
        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';
    }
    else{
        vector<ll> col(n + 1);
        col[1] = 1;
        ll curr = 2;
        for(int i = 2 ; i <= n; i++){
            bool ch = 0;
            for(int j = 1; j < i ; j ++){
                if(mtx[j][i] == mtx[j+1][i] and mtx[j][i] == mtx[j][i-1]){
                    ch = 1;
                    col[i] = col[j];
                }
            }
            if(ch == 0){
                col[i] = curr;
                curr++;
            }
        }
        for(int i =1; i<= n ;i ++){
            cout << col[i] << " ";
        }
        cout << '\n';
        for(int i =1 ;i < n ; i++){
            cout << i << " "<< i + 1<< '\n';
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> tests;
    for (int i = 1; i <= 1; i++){
        solve();
    }
    return 0;
}

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