oj.uz

Submission #611951

# Submission time Handle Problem Language Result Execution time Memory
611951 2022-07-29T09:00:17 Z 이동현(#8500) Izlet (COI19_izlet) C++17
0 / 100
 527 ms 128824 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[1] = ++colN;
    assert(colN <= 2);
    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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 468 KB Integer 0 violates the range [1, 30]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 128824 KB Integer 0 violates the range [1, 3000]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 468 KB Integer 0 violates the range [1, 30]
2 Halted 0 ms 0 KB -