oj.uz

Submission #611955

# Submission time Handle Problem Language Result Execution time Memory
611955 2022-07-29T09:01:27 Z 이동현(#8500) Izlet (COI19_izlet) C++17
100 / 100
 844 ms 147332 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
int a[3004][3004];
int ndis[3004][3004];
int pr[3004], chk[3004], col[3004], colN;
vector<pair<int, int>> ans;

int fd(int x){
    return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}

void unite(int x, int y){
    x = fd(x), y = fd(y);
    pr[x] = y;
}

void dfs(int x){
    chk[x] = 1;
    for(int nxt = 1; nxt <= n; ++nxt){
        if(fd(nxt) != nxt || chk[nxt] || a[x][nxt] != 2){
            continue;
        }
        ans.push_back({x, nxt});
        int didis = (int)1e9, id = 0;
        for(int j = 1; j <= n; ++j){
            if(chk[j]){
                ndis[j][nxt] = ndis[nxt][j] = ndis[j][x] + 1;
                if(a[j][nxt] == a[j][x] && ndis[j][nxt] < didis){
                    didis = ndis[j][nxt];
                    id = j;
                }
            }
        }
        if(id){
            col[nxt] = col[id];
        }
        else{
            col[nxt] = ++colN;
        }
        dfs(nxt);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        pr[i] = i;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];
            if(a[i][j] == 1){
                unite(i, j);
            }
        }
    }
    col[fd(1)] = ++colN;
    dfs(fd(1));
    for(int i = 1; i <= n; ++i){
        cout << col[fd(i)] << ' ';
    }
    cout << '\n';
    for(int i = 1; i <= n; ++i){
        if(i != fd(i)) cout << i << ' ' << fd(i) << '\n';
    }
    for(auto&i:ans){
        cout << i.first << ' ' << i.second << '\n';
    }
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 547 ms 142568 KB Output is correct
3 Correct 563 ms 142640 KB Output is correct
4 Correct 528 ms 100784 KB Output is correct
5 Correct 507 ms 124828 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 129472 KB Output is correct
2 Correct 500 ms 111848 KB Output is correct
3 Correct 745 ms 143488 KB Output is correct
4 Correct 688 ms 143496 KB Output is correct
5 Correct 467 ms 92472 KB Output is correct
6 Correct 525 ms 108460 KB Output is correct
7 Correct 436 ms 91488 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 547 ms 142568 KB Output is correct
3 Correct 563 ms 142640 KB Output is correct
4 Correct 528 ms 100784 KB Output is correct
5 Correct 507 ms 124828 KB Output is correct
6 Correct 516 ms 129472 KB Output is correct
7 Correct 500 ms 111848 KB Output is correct
8 Correct 745 ms 143488 KB Output is correct
9 Correct 688 ms 143496 KB Output is correct
10 Correct 467 ms 92472 KB Output is correct
11 Correct 525 ms 108460 KB Output is correct
12 Correct 436 ms 91488 KB Output is correct
13 Correct 651 ms 136580 KB Output is correct
14 Correct 844 ms 143448 KB Output is correct
15 Correct 554 ms 102384 KB Output is correct
16 Correct 564 ms 90696 KB Output is correct
17 Correct 547 ms 94464 KB Output is correct
18 Correct 672 ms 147332 KB Output is correct
19 Correct 557 ms 131376 KB Output is correct
20 Correct 618 ms 118212 KB Output is correct
21 Correct 661 ms 119204 KB Output is correct
22 Correct 637 ms 126656 KB Output is correct
23 Correct 584 ms 116808 KB Output is correct
24 Correct 706 ms 112376 KB Output is correct
25 Correct 544 ms 104696 KB Output is correct