oj.uz

Submission #611817

# Submission time Handle Problem Language Result Execution time Memory
611817 2022-07-29T07:53:00 Z 반딧불(#8497) Izlet (COI19_izlet) C++17
100 / 100
 1006 ms 92476 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(dsu.find(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);
}

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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 710 ms 92476 KB Output is correct
3 Correct 776 ms 92384 KB Output is correct
4 Correct 1006 ms 87704 KB Output is correct
5 Correct 913 ms 87544 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 45020 KB Output is correct
2 Correct 956 ms 90124 KB Output is correct
3 Correct 707 ms 45336 KB Output is correct
4 Correct 758 ms 45372 KB Output is correct
5 Correct 594 ms 48952 KB Output is correct
6 Correct 705 ms 45480 KB Output is correct
7 Correct 454 ms 39064 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 710 ms 92476 KB Output is correct
3 Correct 776 ms 92384 KB Output is correct
4 Correct 1006 ms 87704 KB Output is correct
5 Correct 913 ms 87544 KB Output is correct
6 Correct 566 ms 45020 KB Output is correct
7 Correct 956 ms 90124 KB Output is correct
8 Correct 707 ms 45336 KB Output is correct
9 Correct 758 ms 45372 KB Output is correct
10 Correct 594 ms 48952 KB Output is correct
11 Correct 705 ms 45480 KB Output is correct
12 Correct 454 ms 39064 KB Output is correct
13 Correct 563 ms 45052 KB Output is correct
14 Correct 785 ms 44932 KB Output is correct
15 Correct 703 ms 51920 KB Output is correct
16 Correct 738 ms 47800 KB Output is correct
17 Correct 643 ms 45704 KB Output is correct
18 Correct 634 ms 45988 KB Output is correct
19 Correct 673 ms 58436 KB Output is correct
20 Correct 669 ms 52164 KB Output is correct
21 Correct 696 ms 53404 KB Output is correct
22 Correct 598 ms 45648 KB Output is correct
23 Correct 643 ms 45160 KB Output is correct
24 Correct 650 ms 45008 KB Output is correct
25 Correct 675 ms 47272 KB Output is correct