oj.uz

Submission #705063

# Submission time Handle Problem Language Result Execution time Memory
705063 2023-03-03T10:12:32 Z Nursik Izlet (COI19_izlet) C++14
43 / 100
 564 ms 74396 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 3e3 + 10, maxm = 20 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int s, n, a[maxn][maxn], p[maxn], sz[maxn], color[maxn], used[maxn];
vector<int> comps[maxn];
int get(int v){
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}
void unite(int a, int b){
    a = get(a), b = get(b);
    if (a == b)
        return;
    if (sz[a] > sz[b])
        swap(a, b);
    p[a] = b;
    sz[b] += sz[a];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cin >> s;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> a[i][j];
        }
    }
    if (s == 1){
    for (int i = 1; i <= n; ++i){
        p[i] = i, sz[i] = 1;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            if (a[i][j] == 1){
                unite(i, j);
            }
        }
    }
    int root = get(1);
    for (int i = 1; i <= n; ++i){
        if (get(i) == root){
            color[i] = 1;
        }
        else{
            color[i] = 2;
        }
        comps[get(i)].pb(i);
        cout << color[i] << " ";
    }
    cout << '\n';
    vector<pair<int, int>> ans;
    for (int i = 1; i <= n; ++i){
        int sz = (int)comps[i].size() - 1;
        for (int j = 0; j < sz; ++j){
            ans.pb(mp(comps[i][j], comps[i][j + 1]));
        }
        if ((int)comps[i].size() > 0 && i != root){
            ans.pb(mp(comps[i][0], root));
        }
    }
    for (auto it : ans){
        cout << it.f << " " << it.s << '\n';
    }
    }
    else if (s == 2){
        int cur = 0;
        for (int i = 1; i <= n; ++i){
            ++cur;
            if (a[1][i] == cur){
                color[i] = i;
            }
            else{
                --cur;
                int prv = 1;
                for (int j = i - 1; j >= 1; --j){
                    if (used[color[j]] == 0){
                        int x = a[j][i];
                        if (x == prv){
                            color[i] = color[j];
                            break;
                        }
                        ++prv;
                    }
                    used[color[j]] = 1;
                }
                for (int j = 1; j <= i; ++j){
                    used[color[j]] = 0;
                }
            }
            cout << color[i] << " ";
        }
        cout << '\n';
        for (int i = 1; i < n; ++i){
            cout << i << " " << i + 1 << '\n';
        }
    }
}
/*
*/

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 393 ms 36412 KB Output is correct
3 Correct 413 ms 37168 KB Output is correct
4 Correct 413 ms 37064 KB Output is correct
5 Correct 387 ms 37144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 36068 KB Output is correct
2 Correct 418 ms 53292 KB Output is correct
3 Correct 537 ms 73464 KB Output is correct
4 Correct 564 ms 74396 KB Output is correct
5 Correct 414 ms 53320 KB Output is correct
6 Correct 458 ms 60328 KB Output is correct
7 Correct 317 ms 49148 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 393 ms 36412 KB Output is correct
3 Correct 413 ms 37168 KB Output is correct
4 Correct 413 ms 37064 KB Output is correct
5 Correct 387 ms 37144 KB Output is correct
6 Correct 426 ms 36068 KB Output is correct
7 Correct 418 ms 53292 KB Output is correct
8 Correct 537 ms 73464 KB Output is correct
9 Correct 564 ms 74396 KB Output is correct
10 Correct 414 ms 53320 KB Output is correct
11 Correct 458 ms 60328 KB Output is correct
12 Correct 317 ms 49148 KB Output is correct
13 Incorrect 430 ms 54180 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -