제출 #582147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582147		MohamedFaresNebili	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	243 ms	22216 KiB

supertrees

#include <bits/stdc++.h>
/// #include "supertrees.h"
#include <ext/pb_ds/assoc_container.hpp>
 
        using namespace std;
        using namespace __gnu_pbds;
 
        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;
 
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
 
        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;
 
        void build(vector<vector<int>> B);
 
        int N, par[1001]; vector<int> S[1001];
        bool vis[1001];
 
        int findSet(int v) {
            if(par[v] == v) return v;
            return par[v] = findSet(par[v]);
        }
        void unionSet(int u, int v) {
            u = findSet(u), v = findSet(v);
            if(S[u].size() < S[v].size()) swap(u, v);
            for(auto e : S[v]) S[u].pb(e);
            par[v] = u; S[v].clear();
        }
 
        int construct(vector<vector<int>> P) {
            N = P.size();
          	vector<vector<int>> B(N, vector<int>(N, 0));
            for(int l = 0; l < N; l++)
                par[l] = l, S[l].pb(l);
            for(int l = 0; l < N; l++) {
                for(int i = l + 1; i < N; i++) {
                    if(findSet(l) == findSet(i) || P[l][i] == 0)
                        continue;
                    unionSet(l, i);
                }
            }
            for(int l = 0; l < N; l++) {
                for(int i = l + 1; i < N; i++) {
                    if(P[l][i] == 0 && findSet(l) == findSet(i))
                        return 0;
                    if(P[l][i] >= 1 && findSet(l) != findSet(i))
                        return 0;
                }
            }
            for(int l = 0; l < N; l++) {
              	if(S[l].size() <= 1) continue;
              	bool Uno = 0, Dos = 0, Tres = 0;
                for(int i = 0; i < S[l].size(); i++)
                    for(int j = i + 1; j < S[l].size(); j++)
                        Uno |= (P[S[l][i]][S[l][j]] == 1),
                        Dos |= (P[S[l][i]][S[l][j]] == 2),
                        Tres |= (P[S[l][i]][S[l][j]] == 3);
                if(Uno && !Dos && !Tres) {
                    for(int i = 1; i < S[l].size(); i++)
                        B[S[l][i]][S[l][i - 1]] = B[S[l][i - 1]][S[l][i]] = 1;
                    continue;
                }
                if(Dos && !Uno && !Tres) {
                    for(int i = 1; i < S[l].size(); i++)
                        B[S[l][i]][S[l][i - 1]] = B[S[l][i - 1]][S[l][i]] = 1;
                    int U = S[l][0], V = S[l][S[l].size() - 1];
                    if(S[l].size() <= 2) return 0;
                    B[U][V] = B[V][U] = 1;
                    continue;
                }
                if(Uno && Dos && !Tres) {
                    vector<int> V;
                    for(int i = 0; i < S[l].size(); i++) {
                        if(vis[S[l][i]]) continue;
                        V.push_back(S[l][i]); int Pr = S[l][i];
                        for(int j = i + 1; j < S[l].size(); j++) {
                            if(P[S[l][i]][S[l][j]] != 1) continue;
                            B[Pr][S[l][j]] = B[S[l][j]][Pr] = 1;
                            Pr = S[l][j]; vis[S[l][j]] = 1;
                        }
                    }
                    if(V.size() <= 2) return 0;
                    for(int l = 1; l < V.size(); l++)
                        B[V[l]][V[l - 1]] = B[V[l - 1]][V[l]] = 1;
                    B[V[0]][V[V.size() - 1]] = B[V[V.size() - 1]][V[0]] = 1;
                    continue;
                }
              	if(Dos) return 0;
                vector<int> V;
                for(int i = 0; i < S[l].size(); i++) {
                    if(vis[S[l][i]]) continue;
                    V.push_back(S[l][i]); int Pr = S[l][i];
                    for(int j = i + 1; j < S[l].size(); j++) {
                        if(P[S[l][i]][S[l][j]] != 1) continue;
                        B[Pr][S[l][j]] = B[S[l][j]][Pr] = 1;
                        Pr = S[l][j]; vis[S[l][j]] = 1;
                    }
                }
                if(V.size() <= 3) return 0;
              	for(int l = 0; l < V.size(); l++) 
                  for(int i = l + 1; i < V.size(); i++)
                    if(P[V[l]][V[i]] != 3) return 0;
                for(int l = 1; l < V.size(); l++)
                    B[V[l]][V[l - 1]] = B[V[l - 1]][V[l]] = 1;
                B[V[0]][V[V.size() - 1]] = B[V[V.size() - 1]][V[0]] = 1;
                B[V[0]][V[V.size() - 2]] = B[V[V.size() - 2]][V[0]] = 1;
            }
            build(B);
            return 1;
        }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:59:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 for(int i = 0; i < S[l].size(); i++)
      |                                ~~^~~~~~~~~~~~~
supertrees.cpp:60:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                     for(int j = i + 1; j < S[l].size(); j++)
      |                                        ~~^~~~~~~~~~~~~
supertrees.cpp:65:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                     for(int i = 1; i < S[l].size(); i++)
      |                                    ~~^~~~~~~~~~~~~
supertrees.cpp:70:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                     for(int i = 1; i < S[l].size(); i++)
      |                                    ~~^~~~~~~~~~~~~
supertrees.cpp:79:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                     for(int i = 0; i < S[l].size(); i++) {
      |                                    ~~^~~~~~~~~~~~~
supertrees.cpp:82:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                         for(int j = i + 1; j < S[l].size(); j++) {
      |                                            ~~^~~~~~~~~~~~~
supertrees.cpp:89:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                     for(int l = 1; l < V.size(); l++)
      |                                    ~~^~~~~~~~~~
supertrees.cpp:96:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int i = 0; i < S[l].size(); i++) {
      |                                ~~^~~~~~~~~~~~~
supertrees.cpp:99:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                     for(int j = i + 1; j < S[l].size(); j++) {
      |                                        ~~^~~~~~~~~~~~~
supertrees.cpp:106:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                for(int l = 0; l < V.size(); l++)
      |                               ~~^~~~~~~~~~
supertrees.cpp:107:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |                   for(int i = l + 1; i < V.size(); i++)
      |                                      ~~^~~~~~~~~~
supertrees.cpp:109:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int l = 1; l < V.size(); l++)
      |                                ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4