oj.uz

답안 #167342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167342 2019-12-07T12:54:51 Z theStaticMind Izlet (COI19_izlet) C++14
100 / 100
 1614 ms 102016 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);
vector<int>tree[3003],T[3003];
vector<int>color(3003,-1);
vector<vector<int>>adj(3003,vector<int>(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;
}
int dfs(int x,int pre,int X,set<int>& S){
      int cnt=-1;
      for(int i=0;i<T[x].size();i++){
            int y=T[x][i];
            if(y==pre)continue;
            bool added=S.insert(color[y]).second;
            if(adj[X][y]!=S.size()){
                  return color[y];
            }
            else {
                  cnt=max(dfs(y,x,X,S),cnt);
                  if(cnt>0)return cnt;
            }
            if(added)
            S.erase(color[y]);
      }
      return cnt;
}
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;
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  cin>>adj[i][j];
            }
      }
      for(int i=0;i<n;i++)no[i]=i;
      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)){
                              tree[i].pb(j);
                              tree[j].pb(i);
                        }
                  }
            }
      }
      for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                  if(adj[i][j]==2){
                        if(merge(i,j)){
                              tree[i].pb(j);
                              tree[j].pb(i);
                        }
                  }
            }
      }
      color[0]=1;
      queue<int>Q;
      Q.push(0);
      int ind=2;
      while(!Q.empty()){
            int x=Q.front();
            Q.pop();
            for(int i=0;i<tree[x].size();i++){
                  int y=tree[x][i];
                  if(color[y]<0){
                        Q.push(y);
                        T[x].pb(y);
                        T[y].pb(x);
                        set<int>S;S.insert(-1);
                        color[y]=dfs(y,-1,y,S);
                        if(color[y]==-1)color[y]=ind++;
                  }
            }
      }
      for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
      for(int i=0;i<n;i++){
            for(int j=0;j<tree[i].size();j++)if(i<tree[i][j])cout<<i+1<<" "<<tree[i][j]+1<<"\n";
      }
}

Compilation message

izlet.cpp: In function 'long long int dfs(long long int, long long int, long long int, std::set<long long int>&)':
izlet.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<T[x].size();i++){
                   ~^~~~~~~~~~~~
izlet.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(adj[X][y]!=S.size()){
izlet.cpp: In function 'int32_t main()':
izlet.cpp:88:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<tree[x].size();i++){
                         ~^~~~~~~~~~~~~~~
izlet.cpp:100:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
       for(int i=0;i<n;i++)cout<<color[i]<<" ";cout<<"\n";
       ^~~
izlet.cpp:100:47: 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:102:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<tree[i].size();j++)if(i<tree[i][j])cout<<i+1<<" "<<tree[i][j]+1<<"\n";
                         ~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 71160 KB Output is correct
2 Correct 808 ms 88808 KB Output is correct
3 Correct 890 ms 88696 KB Output is correct
4 Correct 768 ms 88056 KB Output is correct
5 Correct 796 ms 88540 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 723 ms 86272 KB Output is correct
2 Correct 773 ms 88696 KB Output is correct
3 Correct 1595 ms 102016 KB Output is correct
4 Correct 1614 ms 100524 KB Output is correct
5 Correct 759 ms 89040 KB Output is correct
6 Correct 801 ms 89392 KB Output is correct
7 Correct 614 ms 89960 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 71160 KB Output is correct
2 Correct 808 ms 88808 KB Output is correct
3 Correct 890 ms 88696 KB Output is correct
4 Correct 768 ms 88056 KB Output is correct
5 Correct 796 ms 88540 KB Output is correct
6 Correct 723 ms 86272 KB Output is correct
7 Correct 773 ms 88696 KB Output is correct
8 Correct 1595 ms 102016 KB Output is correct
9 Correct 1614 ms 100524 KB Output is correct
10 Correct 759 ms 89040 KB Output is correct
11 Correct 801 ms 89392 KB Output is correct
12 Correct 614 ms 89960 KB Output is correct
13 Correct 832 ms 89420 KB Output is correct
14 Correct 1239 ms 79868 KB Output is correct
15 Correct 772 ms 88888 KB Output is correct
16 Correct 899 ms 84088 KB Output is correct
17 Correct 864 ms 78624 KB Output is correct
18 Correct 731 ms 84996 KB Output is correct
19 Correct 880 ms 84692 KB Output is correct
20 Correct 766 ms 84512 KB Output is correct
21 Correct 792 ms 83960 KB Output is correct
22 Correct 793 ms 83832 KB Output is correct
23 Correct 880 ms 82808 KB Output is correct
24 Correct 967 ms 77044 KB Output is correct
25 Correct 732 ms 82908 KB Output is correct