제출 #428438

#제출 시각아이디문제언어결과실행 시간메모리
428438alireza_kaviani슈퍼트리 잇기 (IOI20_supertrees)C++17
56 / 100
320 ms32076 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1010; int n , par[MAXN] , sz[MAXN] , mark[MAXN] , adj[MAXN][MAXN] , ans[MAXN][MAXN]; vector<int> vec , comp[MAXN]; int Find(int v){ return (par[v] == -1 ? v : par[v] = Find(par[v])); } void Union(int v , int u){ v = Find(v); u = Find(u); if(v == u) return; if(sz[v] < sz[u]) swap(v , u); par[u] = v; sz[v] += sz[u]; } void DFS(int v){ mark[v] = 1; vec.push_back(v); for(int u = 0 ; u < n ; u++){ if(adj[v][u] > 0 && mark[u] == 0) DFS(u); } } int solve(vector<int> v){ vector<int> vec; for(int i : v){ if(Find(i) == i){ vec.push_back(i); } } int m = vec.size(); for(int i = 0 ; i < m ; i++){ int v = vec[i] , u = vec[(i + 1) % m]; if(v != u) ans[v][u] = ans[u][v] = 1; } int flag2 = 0 , flag3 = 0; for(int i : v){ for(int j : v){ if(adj[i][j] == 2) flag2 = 1; if(adj[i][j] == 3) flag3 = 1; } } if(flag2 && flag3) return 0; return 1; } int construct(vector<vector<int>> p) { fill(par , par + MAXN , -1); fill(sz , sz + MAXN , 1); n = p.size(); vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row(n , 0); answer.push_back(row); for(int j = 0 ; j < n ; j++){ adj[i][j] = p[i][j]; if(adj[i][j] == 1) Union(i , j); } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if(Find(i) == Find(j) && adj[i][j] != 1) return 0; } comp[Find(i)].push_back(i); } for(int i = 0 ; i < n ; i++){ if(comp[i].size() == 0) continue; for(int j = 0 ; j + 1 < comp[i].size() ; j++){ if(comp[i][j] == i){ swap(comp[i][j] , comp[i][comp[i].size() - 1]); } } for(int j = 0 ; j + 1 < comp[i].size() ; j++){ int v = comp[i][j] , u = comp[i][j + 1]; ans[v][u] = ans[u][v] = 1; } } for(int i = 0 ; i < n ; i++){ if(!mark[i]){ vec.clear(); DFS(i); for(int j : vec){ for(int k : vec){ if(adj[j][k] == 0) return 0; } } if(solve(vec) == 0) return 0; } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ answer[i][j] = ans[i][j]; } } build(answer); return 1; }

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:72:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int j = 0 ; j + 1 < comp[i].size() ; j++){
      |                   ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:77:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int j = 0 ; j + 1 < comp[i].size() ; j++){
      |                   ~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...