oj.uz

Submission #1041723

# Submission time Handle Problem Language Result Execution time Memory
1041723 2024-08-02T07:25:02 Z vjudge1 Izlet (COI19_izlet) C++17
43 / 100
 409 ms 91088 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 260 ms 71248 KB Output is correct
3 Correct 258 ms 71252 KB Output is correct
4 Correct 314 ms 70996 KB Output is correct
5 Correct 279 ms 70924 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 71072 KB Output is correct
2 Correct 355 ms 80540 KB Output is correct
3 Correct 409 ms 90980 KB Output is correct
4 Correct 381 ms 91088 KB Output is correct
5 Correct 301 ms 80468 KB Output is correct
6 Correct 354 ms 84148 KB Output is correct
7 Correct 242 ms 61444 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 260 ms 71248 KB Output is correct
3 Correct 258 ms 71252 KB Output is correct
4 Correct 314 ms 70996 KB Output is correct
5 Correct 279 ms 70924 KB Output is correct
6 Correct 303 ms 71072 KB Output is correct
7 Correct 355 ms 80540 KB Output is correct
8 Correct 409 ms 90980 KB Output is correct
9 Correct 381 ms 91088 KB Output is correct
10 Correct 301 ms 80468 KB Output is correct
11 Correct 354 ms 84148 KB Output is correct
12 Correct 242 ms 61444 KB Output is correct
13 Incorrect 335 ms 80976 KB Output isn't correct
14 Halted 0 ms 0 KB -