제출 #583442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583442		TimDee	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	198 ms	22076 KiB

supertrees

    #include "supertrees.h"
     
    #include <bits/stdc++.h>
    using namespace std;
    #define forn(i,n) for (int i=0; i<n; ++i)
    #define all(a) a.begin(), a.end()
    #define pb(x) push_back(x)
    #define mp(x,y) make_pair(x,y)
    #define pi pair<int,int>
    #define f first
    #define s second
     
    int mirror(vector<vector<int>>&a) {
      int n=a.size();
      for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
          if (a[i][j]!=a[j][i]) return 0;
        }
      }
      return 1;
    }
     
    int construct(std::vector<std::vector<int>> p) {
      int n = p.size();
      
      vector<vector<int>> a(n); 
      forn(i,n) a[i].assign(n,0);
     
      if (!mirror(p)) return 0;
     
      queue<int> q;
      q.push(0);
     
      vector<pair<int,int>> edges;
      vector<int> vis(n,0);
     
      while (!q.empty()) {
     
      int v=q.front(); q.pop();
      if (vis[v]) continue;
     
      vis[v]=1;
     
      vector<int> two;
      for (int i=0; i<n; ++i) {
        if (vis[i]) continue;
        if (p[v][i]==1) {vis[i]=1; edges.pb(mp(v,i)); }
        else if (p[v][i]==2) two.pb(i);
        else q.push(i);
      }
     
      pi P = {-1,-1};
     
      if (!two.size()) continue;
      if (two.size()==1) return 0;
      for (int i=0; i<two.size(); ++i) {
        for (int j=i+1; j<two.size(); ++j) {
          if (p[two[i]][two[j]]==2) P={two[i],two[j]};
        }
      }
     
      if (P.f==-1 && P.s==-1) return 0;
     
      int X=P.f, Y=P.s;
      vis[X]=vis[Y]=1;
      edges.pb(mp(v,X)); edges.pb(mp(v,Y)); edges.pb(mp(X,Y));
     
      for (auto u:two) {
        vis[u]=1;
        if (u==X || u==Y) continue;
        if (p[X][u]==2 && p[Y][u]==2) return 0;
        if (p[X][u]==1) edges.pb(mp(X,u));
        else edges.pb(mp(Y,u));
      }
     
      }
     
      for (auto E:edges) {
        int u=E.f, v=E.s;
        a[u][v]=1;
        a[v][u]=1;
      }
     
      build(a);
      return 1;
    }

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |       for (int i=0; i<two.size(); ++i) {
      |                     ~^~~~~~~~~~~
supertrees.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j=i+1; j<two.size(); ++j) {
      |                         ~^~~~~~~~~~~

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