이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 1005;
#ifndef death
#include "supertrees.h"
#endif
#ifdef death
void build(vector<vector<int>> b)
{
for (int i = 0; i < b.size(); i++)
{
for (int j = 0; j < b.size(); j++)
cout << b[i][j] << " ";
cout << endl;
}
}
#endif
int parent[N];
void init(int n)
{
for (int i = 0; i < n; i++)
parent[i] = i;
}
int par(int v)
{
if (v == parent[v])
return v;
return parent[v] = par(parent[v]);
}
void dsu(int a, int b)
{
a = par(a);
b = par(b);
if (a == b)
return;
parent[b] = a;
}
int n,z;
vector<vector<int>> ans,p;
void add(int a, int b)
{
ans[a][b] = ans[b][a] = 1;
}
void solve(vector<int> v)
{
init(v.size());
for (int i = 0; i < v.size(); i++)
for (int j = i + 1; j < v.size(); j++)
if (p[v[i]][v[j]] == 1)
dsu(i, j);
for (int i = 0; i < v.size(); i++)
for (int j = i + 1; j < v.size(); j++)
if (p[v[i]][v[j]] == 2 && par(i) == par(j))
{
z = 1;
return;
}
map<int, vector<int>> VS;
vector<int> V;
for (int i = 0; i < v.size(); i++)
VS[v[par(i)]].PB(v[i]);
for (auto it = VS.begin(); it != VS.end(); ++it)
{
for (int i = 0; i < it->second.size() - 1; i++)
add(it->second[i], it->second[i + 1]);
V.push_back(it->first);
}
if(V.size()>1)
for (int i = 0; i < V.size(); i++)
add(V[i], V[(i + 1) % V.size()]);
}
int construct(vector<vector<int>> P)
{
p = P;
n = p.size();
ans.resize(n, vector<int>(n,0));
init(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (p[i][j])
{
dsu(i, j);
if (p[i][j] == 3)
return 0;
}
map<int, vector<int>> vs;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
if (p[i][j] == 0 && par(i) == par(j))
return 0;
vs[par(i)].push_back(i);
}
for (auto it = vs.begin(); it != vs.end(); ++it)
solve(it->second);
if (z)
return 0;
build(ans);
return 1;
}
#ifdef death
int main()
{
fastIO;
vector<vector<int>> P;
int nn;
cin >> nn;
for (int i = 0; i < nn; i++)
{
P.push_back(vector<int>());
for (int j = 0; j < nn; j++)
{
int x;
cin >> x;
P[i].push_back(x);
}
}
cout << construct(P) << endl;
return 0;
}
#endif
/*
4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
*/
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'void solve(std::vector<int>)':
supertrees.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j = i + 1; j < v.size(); j++)
| ~~^~~~~~~~~~
supertrees.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:92:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int j = i + 1; j < v.size(); j++)
| ~~^~~~~~~~~~
supertrees.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < it->second.size() - 1; i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < V.size(); i++)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |