oj.uz

Submission #611974

# Submission time Handle Problem Language Result Execution time Memory
611974 2022-07-29T09:15:31 Z 조영욱(#8499) Izlet (COI19_izlet) C++17
100 / 100
 889 ms 39792 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int arr[3001][3001];
int col[3001];
int cnt=0;
int used[3001];
int p[3001];
typedef pair<int,int> P;
vector<P> edge;
int vec[3005];
bool vis[3005];
bool vis2[3005];
int sz=0;

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

void dfs(int v) {
    vis[v]=true;
    for(int i=1;i<=n;i++) {
        if (i==find(i)&&arr[v][i]==2&&!vis[i]) {
            edge.push_back(P(v,i));
            dfs(i);
        }
    }
}

vector<int> adj[3001];
int st;

int dfs1(int v) {
    vis2[v]=true;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (vis2[nt]||col[nt]==0) {
            continue;
        }
        if (!used[col[nt]]&&arr[st][v]==arr[st][nt]) {
            return col[nt];
        }
        used[col[nt]]++;
        int got=dfs1(nt);
        used[col[nt]]--;
        if (got!=cnt+1) {
            return got;
        }
    }
    return cnt+1;
}

vector<P> save;

int main() {
    int s;
    scanf("%d",&s);
    scanf("%d",&n);
    memset(p,-1,sizeof(p));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            scanf("%d",&arr[i][j]);
            if (arr[i][j]==1&&i!=j&&find(i)!=find(j)) {
                save.push_back(P(i,j));
                merge(i,j);
            }
        }
    }
    col[1]=1;
    dfs(find(1));
    for(int i=0;i<edge.size();i++) {
        adj[edge[i].first].push_back(edge[i].second);
        adj[edge[i].second].push_back(edge[i].first);
    }
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1]=true;
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        st=now;
        memset(vis2,0,sizeof(vis2));
        memset(used,0,sizeof(used));
        int x=dfs1(now);
        if (x>cnt) {
            cnt++;
        }
        col[now]=x;
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i];
            if (!vis[nt]) {
                vis[nt]=true;
                q.push(nt);
            }
        }
    }
    assert(find(1)==1);
    assert(edge.size()+save.size()==n-1);
for(int i=1;i<=n;i++) printf("%d ",col[find(i)]);
printf("\n");
for(int i=0;i<edge.size();i++) printf("%d %d\n",edge[i].first,edge[i].second);
for(int i=0;i<save.size();i++) printf("%d %d\n",save[i].first,save[i].second);
    return 0;
}

Compilation message

izlet.cpp: In function 'int dfs1(int)':
izlet.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
izlet.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from izlet.cpp:1:
izlet.cpp:109:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     assert(edge.size()+save.size()==n-1);
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
izlet.cpp:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 | for(int i=0;i<edge.size();i++) printf("%d %d\n",edge[i].first,edge[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:113:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 | for(int i=0;i<save.size();i++) printf("%d %d\n",save[i].first,save[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d",&s);
      |     ~~~~~^~~~~~~~~
izlet.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
izlet.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 689 ms 36468 KB Output is correct
3 Correct 702 ms 36376 KB Output is correct
4 Correct 709 ms 36072 KB Output is correct
5 Correct 767 ms 36144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 36280 KB Output is correct
2 Correct 761 ms 37148 KB Output is correct
3 Correct 873 ms 36788 KB Output is correct
4 Correct 801 ms 36784 KB Output is correct
5 Correct 737 ms 37200 KB Output is correct
6 Correct 830 ms 36568 KB Output is correct
7 Correct 523 ms 30748 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 689 ms 36468 KB Output is correct
3 Correct 702 ms 36376 KB Output is correct
4 Correct 709 ms 36072 KB Output is correct
5 Correct 767 ms 36144 KB Output is correct
6 Correct 706 ms 36280 KB Output is correct
7 Correct 761 ms 37148 KB Output is correct
8 Correct 873 ms 36788 KB Output is correct
9 Correct 801 ms 36784 KB Output is correct
10 Correct 737 ms 37200 KB Output is correct
11 Correct 830 ms 36568 KB Output is correct
12 Correct 523 ms 30748 KB Output is correct
13 Correct 730 ms 36172 KB Output is correct
14 Correct 889 ms 37488 KB Output is correct
15 Correct 730 ms 39548 KB Output is correct
16 Correct 740 ms 37444 KB Output is correct
17 Correct 801 ms 37444 KB Output is correct
18 Correct 635 ms 39576 KB Output is correct
19 Correct 669 ms 39792 KB Output is correct
20 Correct 664 ms 39724 KB Output is correct
21 Correct 700 ms 37212 KB Output is correct
22 Correct 729 ms 37160 KB Output is correct
23 Correct 646 ms 37232 KB Output is correct
24 Correct 691 ms 37388 KB Output is correct
25 Correct 631 ms 38264 KB Output is correct