oj.uz

Submission #611816

# Submission time Handle Problem Language Result Execution time Memory
611816 2022-07-29T07:51:51 Z 반딧불(#8497) Izlet (COI19_izlet) C++17
0 / 100
 613 ms 90528 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[3002];
    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }
    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }
    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

int n, k;
int arr[3002][3002];
vector<int> link[3002];
bool able[3002][3002];
bool visited[3002];
int col[3002];

void firstDfs(int x, int p=-1){
    visited[x] = 1;
    vector<int> newLink;
    if(p!=-1) newLink.push_back(p);
    for(auto y: link[x]){
        if(visited[y]) continue;
        firstDfs(y, x);
        newLink.push_back(y);
    }
    link[x].swap(newLink);
}

void makeTree(){
    fill(visited+1, visited+n+1, 0);
    firstDfs(1);
}

int cnt[3002];
vector<pair<int, int> > ans;
int getColor(int x, int p, int root, int dist){
    if(p!=-1){
        cnt[col[x]]++;
        if(cnt[col[x]] == 1) dist++;
        if(dist != arr[root][x]) return col[x];
    }
    for(auto y: link[x]){
        if(y==p || !visited[y]) continue;
        int tmp = getColor(y, x, root, dist);
        if(tmp) return tmp;
    }
    if(p!=-1){
        cnt[col[x]]--;
        if(cnt[col[x]] == 0) dist--;
    }
    return 0;
}

void dfs(int x, int p=-1){ /// x�� ���� ������ �����Ѵ�
    visited[x] = 1;
    fill(cnt+1, cnt+k+1, 0);
    col[x] = getColor(x, -1, x, 1);
    if(!col[x]) col[x] = ++k;
    for(auto y: link[x]){
        if(visited[y]) continue;
        dfs(y, x);
    }
}

int main(){
    scanf("%d %d", &n, &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    dsu.init(n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j] == 1) dsu.merge(i, j);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][j] == 2){
                link[dsu.find(i)].push_back(dsu.find(j));
            }
        }
    }
    for(int i=1; i<=n; i++){
        sort(link[i].begin(), link[i].end());
        link[i].erase(unique(link[i].begin(), link[i].end()), link[i].end());
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) able[i][j] = 1;
    makeTree();
//    for(int i=1; i<=n; i++){
//        printf("%d: ", i);
//        for(auto j: link[i]) printf("%d ", j);
//        puts("");
//    }

    fill(visited+1, visited+n+1, 0);
    dfs(dsu.find(1));
    for(int i=1; i<=n; i++){
        col[i] = col[dsu.find(i)];
        if(i!=dsu.find(i)) ans.push_back(make_pair(i, dsu.find(i)));
        for(auto j: link[i]){
            if(j>i) ans.push_back(make_pair(i, j));
        }
    }
    for(int i=1; i<=n; i++) printf("%d ", col[i]);
    puts("");
    for(auto p: ans) printf("%d %d\n", p.first, p.second);
    assert((int)ans.size() == n-1);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &n, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izlet.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d", &arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 90528 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -