oj.uz

Submission #611933

# Submission time Handle Problem Language Result Execution time Memory
611933 2022-07-29T08:55:31 Z 조영욱(#8499) Izlet (COI19_izlet) C++17
43 / 100
 995 ms 36572 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;
    vec[sz++]=v;
    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);
        }
    }
    sz--;
}

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]) {
            continue;
        }
        if (col[v]!=0&&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:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:83: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]
   83 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
izlet.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         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:111: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]
  111 |     assert(edge.size()+save.size()==n-1);
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
izlet.cpp:114: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]
  114 | for(int i=0;i<edge.size();i++) printf("%d %d\n",edge[i].first,edge[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:115: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]
  115 | for(int i=0;i<save.size();i++) printf("%d %d\n",save[i].first,save[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d",&s);
      |     ~~~~~^~~~~~~~~
izlet.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
izlet.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |             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 588 ms 36204 KB Output is correct
3 Correct 623 ms 36212 KB Output is correct
4 Correct 667 ms 35844 KB Output is correct
5 Correct 645 ms 35984 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 35992 KB Output is correct
2 Correct 659 ms 36384 KB Output is correct
3 Correct 839 ms 36560 KB Output is correct
4 Correct 995 ms 36572 KB Output is correct
5 Correct 750 ms 36260 KB Output is correct
6 Correct 829 ms 36256 KB Output is correct
7 Correct 499 ms 30744 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 588 ms 36204 KB Output is correct
3 Correct 623 ms 36212 KB Output is correct
4 Correct 667 ms 35844 KB Output is correct
5 Correct 645 ms 35984 KB Output is correct
6 Correct 661 ms 35992 KB Output is correct
7 Correct 659 ms 36384 KB Output is correct
8 Correct 839 ms 36560 KB Output is correct
9 Correct 995 ms 36572 KB Output is correct
10 Correct 750 ms 36260 KB Output is correct
11 Correct 829 ms 36256 KB Output is correct
12 Correct 499 ms 30744 KB Output is correct
13 Incorrect 604 ms 35836 KB Output isn't correct
14 Halted 0 ms 0 KB -