제출 #1041718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041718		vjudge1	Izlet (COI19_izlet)	C++17	18 / 100	449 ms	71352 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));
    set<ll>st;
    for(int i = 1; i<= n ; i++){
        for(int j = 1; j<= n ;j ++){
            cin >> mtx[i][j];
            st.insert(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(st.size() < 3){
        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);
    int tests = 1;
    cin >> tests;
    if(tests == 1 or tests  == 2){
        for (int i = 1; i <= tests; i++){
            solve();
        }
    }
    return 0;
}

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