oj.uz

Submission #611972

# Submission time Handle Problem Language Result Execution time Memory
611972 2022-07-29T09:12:45 Z 조영욱(#8499) Izlet (COI19_izlet) C++17
43 / 100
 993 ms 41164 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int arr[3001][3001];
int col[3001];
int cnt=0;
bool 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 (col[nt]!=0&&!used[col[nt]]&&arr[st][v]==arr[st][nt]) {
            return col[nt];
        }
        used[col[nt]]=true;
        int got=dfs1(nt);
        used[col[nt]]=false;
        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 508 KB Output is correct
2 Correct 703 ms 36764 KB Output is correct
3 Correct 756 ms 36744 KB Output is correct
4 Correct 703 ms 36496 KB Output is correct
5 Correct 699 ms 36528 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 36636 KB Output is correct
2 Correct 774 ms 41164 KB Output is correct
3 Correct 807 ms 38048 KB Output is correct
4 Correct 993 ms 38016 KB Output is correct
5 Correct 690 ms 41036 KB Output is correct
6 Correct 722 ms 37472 KB Output is correct
7 Correct 573 ms 31932 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 703 ms 36764 KB Output is correct
3 Correct 756 ms 36744 KB Output is correct
4 Correct 703 ms 36496 KB Output is correct
5 Correct 699 ms 36528 KB Output is correct
6 Correct 655 ms 36636 KB Output is correct
7 Correct 774 ms 41164 KB Output is correct
8 Correct 807 ms 38048 KB Output is correct
9 Correct 993 ms 38016 KB Output is correct
10 Correct 690 ms 41036 KB Output is correct
11 Correct 722 ms 37472 KB Output is correct
12 Correct 573 ms 31932 KB Output is correct
13 Incorrect 720 ms 37336 KB Output isn't correct
14 Halted 0 ms 0 KB -