oj.uz

Submission #611914

# Submission time Handle Problem Language Result Execution time Memory
611914 2022-07-29T08:45:47 Z 조영욱(#8499) Izlet (COI19_izlet) C++17
43 / 100
 888 ms 37464 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);
            }
        }
    }
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++) {
      |                     ~^~~~~~~~~~~~~~~~
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: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 667 ms 36688 KB Output is correct
3 Correct 653 ms 36652 KB Output is correct
4 Correct 707 ms 36336 KB Output is correct
5 Correct 829 ms 36544 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 36424 KB Output is correct
2 Correct 721 ms 37464 KB Output is correct
3 Correct 829 ms 37092 KB Output is correct
4 Correct 888 ms 37176 KB Output is correct
5 Correct 677 ms 37320 KB Output is correct
6 Correct 669 ms 36952 KB Output is correct
7 Correct 486 ms 31008 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 667 ms 36688 KB Output is correct
3 Correct 653 ms 36652 KB Output is correct
4 Correct 707 ms 36336 KB Output is correct
5 Correct 829 ms 36544 KB Output is correct
6 Correct 735 ms 36424 KB Output is correct
7 Correct 721 ms 37464 KB Output is correct
8 Correct 829 ms 37092 KB Output is correct
9 Correct 888 ms 37176 KB Output is correct
10 Correct 677 ms 37320 KB Output is correct
11 Correct 669 ms 36952 KB Output is correct
12 Correct 486 ms 31008 KB Output is correct
13 Incorrect 686 ms 37248 KB Output isn't correct
14 Halted 0 ms 0 KB -