oj.uz

Submission #611965

# Submission time Handle Problem Language Result Execution time Memory
611965 2022-07-29T09:04:22 Z 조영욱(#8499) Izlet (COI19_izlet) C++17
18 / 100
 969 ms 39008 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) {

}

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);
            }
        }
    }
queue<int> que;
que.push(1);
vis[1]=true;
while (!que.empty()) {
int v=que.front();
que.pop();
    for(int i=1;i<=n;i++) {
        if (i==find(i)&&arr[v][i]==2&&!vis[i]) {
            edge.push_back(P(v,i));
vis[i]=true;
que.push(i);
        }
    }
}
    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:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:87: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]
   87 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
izlet.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         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:115: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]
  115 |     assert(edge.size()+save.size()==n-1);
      |            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
izlet.cpp:118: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]
  118 | for(int i=0;i<edge.size();i++) printf("%d %d\n",edge[i].first,edge[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:119: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]
  119 | for(int i=0;i<save.size();i++) printf("%d %d\n",save[i].first,save[i].second);
      |             ~^~~~~~~~~~~~
izlet.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d",&s);
      |     ~~~~~^~~~~~~~~
izlet.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
izlet.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             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 757 ms 36336 KB Output is correct
3 Correct 723 ms 36336 KB Output is correct
4 Correct 671 ms 36416 KB Output is correct
5 Correct 731 ms 36256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 36448 KB Output is correct
2 Correct 722 ms 39008 KB Output is correct
3 Correct 950 ms 38112 KB Output is correct
4 Correct 969 ms 38084 KB Output is correct
5 Correct 706 ms 38920 KB Output is correct
6 Incorrect 788 ms 37140 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 757 ms 36336 KB Output is correct
3 Correct 723 ms 36336 KB Output is correct
4 Correct 671 ms 36416 KB Output is correct
5 Correct 731 ms 36256 KB Output is correct
6 Correct 707 ms 36448 KB Output is correct
7 Correct 722 ms 39008 KB Output is correct
8 Correct 950 ms 38112 KB Output is correct
9 Correct 969 ms 38084 KB Output is correct
10 Correct 706 ms 38920 KB Output is correct
11 Incorrect 788 ms 37140 KB Output isn't correct
12 Halted 0 ms 0 KB -