oj.uz

Submission #1041521

# Submission time Handle Problem Language Result Execution time Memory
1041521 2024-08-02T05:09:26 Z vjudge1 Izlet (COI19_izlet) C++17
18 / 100
 301 ms 71312 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));
    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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 264 ms 71312 KB Output is correct
3 Correct 269 ms 71252 KB Output is correct
4 Correct 301 ms 70992 KB Output is correct
5 Correct 298 ms 70740 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 264 ms 71312 KB Output is correct
3 Correct 269 ms 71252 KB Output is correct
4 Correct 301 ms 70992 KB Output is correct
5 Correct 298 ms 70740 KB Output is correct
6 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -