oj.uz

Submission #1041718

# Submission time Handle Problem Language Result Execution time Memory
1041718 2024-08-02T07:22:53 Z vjudge1 Izlet (COI19_izlet) C++17
18 / 100
 449 ms 71352 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 328 ms 71324 KB Output is correct
3 Correct 303 ms 71316 KB Output is correct
4 Correct 317 ms 70996 KB Output is correct
5 Correct 339 ms 70920 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 449 ms 71352 KB Extra information in the output file
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 328 ms 71324 KB Output is correct
3 Correct 303 ms 71316 KB Output is correct
4 Correct 317 ms 70996 KB Output is correct
5 Correct 339 ms 70920 KB Output is correct
6 Incorrect 449 ms 71352 KB Extra information in the output file
7 Halted 0 ms 0 KB -