이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "supertrees.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
set<int>tree[1001];
bool vis[1001];
int pai[1001];
// void build(vector<vector<int>>b){
// vector<ii>edges;
// int n = sz(b[0]);
// for(int i=0;i<n;++i){
// for(int j=i+1;j<n;++j){
// if(b[i][j])edges.pb({i,j});
// }
// }
// for(auto [x,y]:edges)cout<<x<<" "<<y<<endl;
// }
int construct(vector<vector<int>>v){
int n = sz(v[0]);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(v[i][j]>2)return 0;//impossivel se v[i][j] == 3
if(v[i][j]==1)tree[i].insert(j);//mesma arvore
}
assert(tree[i].count(i));//enunciado nao deixou isso claro
}
vector<vector<int>>ans(n,vector<int>(n));
for(int i=0;i<n;++i){
if(!vis[i]){
vis[i] = 1, pai[i] = i;
for(auto x:tree[i]){
vis[x] = 1, pai[x] = i, ans[i][x] = ans[x][i] = 1;
if(tree[x]!=tree[i])return 0;
}
}
}
//as arvores estao todas certas!
for(int i=0;i<n;++i)vis[i] = 0;
for(int i=0;i<n;++i){
if(vis[pai[i]])continue;
int x = pai[i];
vis[x] = 1;
set<int>ciclo={x};
for(int j=0;j<n;++j)if(v[x][pai[j]]==2)ciclo.insert(pai[j]);
int ultimo = *ciclo.rbegin();
if(sz(ciclo)==1)continue;//nao tem ciclo
if(sz(ciclo)==2)return 0;//nao existe ciclo de tamanho 2
for(auto y:ciclo){
ans[ultimo][y] = ans[x][ultimo] = 1, vis[y] = 1, ultimo = y;
for(int j=0;j<n;++j){
if(pai[j]==y)continue;
if(ciclo.count(pai[j])==0){
if(v[y][j]!=0)return 0;
}else{
if(v[y][j]!=2)return 0;
}
}
}
}
build(ans);
return 1;
}
// int main(){
// int n;cin>>n;
// vector<vector<int>>v(n,vector<int>(n));
// for(int i=0;i<n;++i)for(int j=0;j<n;++j)cin>>v[i][j];
// cout<<construct(v)<<endl;
// }
# | 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... |