oj.uz

Submission #167318

# Submission time Handle Problem Language Result Execution time Memory
167318 2019-12-07T10:27:56 Z theStaticMind Izlet (COI19_izlet) C++14
43 / 100
 1076 ms 85496 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<int>no(3003);
int F(int x){
      if(no[x]==x)return x;
      return no[x]=F(no[x]);
}
bool merge(int x,int y){
      x=F(x);
      y=F(y);
      if(x==y)return false;
      if(x<y)swap(x,y);
      no[x]=y;
      return true;
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int k;
      cin>>k;
      int n;
      cin>>n;
      vector<vector<int>>adj(n,vector<int>(n));
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  cin>>adj[i][j];
            }
      }
      vector<int>color(n,-1);
      for(int i=0;i<n;i++)no[i]=i;
      if(k==1){
            vector<ii>edge;
            for(int i=0;i<n;i++){
                  for(int j=0;j<n;j++){
                        if(i==j)continue;
                        if(adj[i][j]==1){
                              if(merge(i,j)){
                                    edge.pb({i,j});
                              }
                        }
                  }
            }
            color[0]=1;
            for(int i=0;i<n;i++){
                  if(F(i)==0)color[i]=1;
                  else color[i]=2;
            }
            for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
            for(int i=0;i<edge.size();i++)cout<<edge[i].first+1<<" "<<edge[i].second+1<<"\n";
            for(int i=0;i<n;i++){
                  if(F(i)==i){
                        if(merge(i,0)){
                              cout<<1<<" "<<i+1<<"\n";
                        }
                  }
            }
      }
      if(k==2){
            color[0]=1;
            for(int i=1;i<n;i++){
                  if(adj[0][i]!=adj[0][i-1])color[i]=adj[0][i];
            }
            for(int i=0;i<n;i++){
                  if(color[i]>0)continue;
                  set<int>vis;
                  for(int j=i-1;j>=0;j--){
                        if(!vis.count(color[j])&&adj[i][j]==adj[i][j+1]){
                              color[i]=color[j];
                              break;
                        }
                        vis.insert(color[j]);
                  }
                  if(color[i]==-1)color[i]=1;
            }
            for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
            for(int i=1;i<=n-1;i++)cout<<i<<" "<<i+1<<"\n";
      }
}

Compilation message

izlet.cpp: In function 'int32_t main()':
izlet.cpp:58:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
             ^~~
izlet.cpp:58:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
                                                     ^~~~
izlet.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<edge.size();i++)cout<<edge[i].first+1<<" "<<edge[i].second+1<<"\n";
                         ~^~~~~~~~~~~~
izlet.cpp:85:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
             ^~~
izlet.cpp:85:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
                                                     ^~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 699 ms 82020 KB Output is correct
3 Correct 677 ms 77060 KB Output is correct
4 Correct 804 ms 77048 KB Output is correct
5 Correct 713 ms 76664 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 77504 KB Output is correct
2 Correct 657 ms 80688 KB Output is correct
3 Correct 1076 ms 84156 KB Output is correct
4 Correct 889 ms 84088 KB Output is correct
5 Correct 684 ms 81272 KB Output is correct
6 Correct 728 ms 85496 KB Output is correct
7 Correct 569 ms 62072 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 699 ms 82020 KB Output is correct
3 Correct 677 ms 77060 KB Output is correct
4 Correct 804 ms 77048 KB Output is correct
5 Correct 713 ms 76664 KB Output is correct
6 Correct 707 ms 77504 KB Output is correct
7 Correct 657 ms 80688 KB Output is correct
8 Correct 1076 ms 84156 KB Output is correct
9 Correct 889 ms 84088 KB Output is correct
10 Correct 684 ms 81272 KB Output is correct
11 Correct 728 ms 85496 KB Output is correct
12 Correct 569 ms 62072 KB Output is correct
13 Incorrect 684 ms 77376 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -