| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1069943 | 2024-08-22T10:24:32 Z | hasan2006 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 152 ms | 22188 KB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 2e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N];
//int press(string a){}
int construct(vector<vector<int>> v){
ll i , j , l , r , s = 0, f , n , m , x , y , k;
n = v.size();
vector<vector<int>>c(n);
for(i = 0; i < n; i++)
c[i].resize(n);
for(i = 0; i < n; i++){
if(b[i] != 0)
continue;
vector<pair<int,pair<int,int>>>vc;
vector<int>v1 , v2 , v3;
for(j = 0; j < n; j++)
if(v[i][j] != 0){
b[j] = 1 , v1.pb(j);
}
l = r = 0;
for(x = 0; x < v1.size(); x++){
if(b[v1[x]] != 2)
b[v1[x]] = 3;
f = v1[x];
for(y = x + 1; y < v1.size(); y++){
vc.pb({v[v1[x]][v1[y]] , {v1[x] , v1[y]}});
if(v[v1[x]][v1[y]] == 2)
l = 1;
else if(v[v1[x]][v1[y]] == 3)
r = 1;
else if(b[v1[x]] == 3){
//if(b[v1[y]] == 2)
// return 0;
c[v1[y]][f] = c[f][v1[y]] = 1;
b[v1[y]] = 2;
f = v1[y];
}
}
}
sort(all(vc));
if(v1.size() == 1)
continue;
if((l == 1 && r == 1) || vc.front().fi == 0)
return 0;
set<int>st;
for(auto to : v1){
st.insert(to);
if(b[to] == 3)
v2.pb(to);
else
v3.pb(to);
}
if(v2.size()){
if(v2.size() <= vc.back().fi){
return 0;
}
f = v2.back();
for(auto to : v2)
c[f][to] = c[to][f] = 1 , f = to;
if(vc.back().fi == 3)
c[v2[0]][v2[2]] = c[v2[2]][v2[0]] = 1;
}
for(auto to : v1){
ll L = 0 ,R = 0 , s =0;
for(j = 0; j < n ; j++)
if(v[to][j] != 0){
if(st.find(j) == st.end())
return 0;
s++;
if(to == j)
continue;
if(v[to][j] == 2)
L = 1;
else if(v[to][j] == 3)
R = 1;
else {
// if(b[to] == 1 || b[j] == 1)
// return 0;
}
}
if((L > l) || (R > r) || s != v1.size())
return 0;
}
}
// for(i = 0; i < n; i++){
// for(j = 0; j < n; j++)
// cout<<c[i][j]<<" ";
// cout<<"\n";
// }
build(c);
return 1;
}
/*
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout<<construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
}*/
// Author : حسن
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Incorrect | 0 ms | 348 KB | Answer gives possible 0 while actual possible 1 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Incorrect | 0 ms | 348 KB | Answer gives possible 0 while actual possible 1 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Correct | 0 ms | 348 KB | Output is correct |
| 4 | Correct | 0 ms | 348 KB | Output is correct |
| 5 | Correct | 0 ms | 348 KB | Output is correct |
| 6 | Correct | 0 ms | 348 KB | Output is correct |
| 7 | Correct | 0 ms | 348 KB | Output is correct |
| 8 | Correct | 5 ms | 1112 KB | Output is correct |
| 9 | Correct | 120 ms | 22096 KB | Output is correct |
| 10 | Correct | 1 ms | 348 KB | Output is correct |
| 11 | Correct | 0 ms | 348 KB | Output is correct |
| 12 | Correct | 6 ms | 1308 KB | Output is correct |
| 13 | Correct | 141 ms | 21992 KB | Output is correct |
| 14 | Correct | 0 ms | 344 KB | Output is correct |
| 15 | Correct | 0 ms | 348 KB | Output is correct |
| 16 | Correct | 6 ms | 860 KB | Output is correct |
| 17 | Correct | 65 ms | 13960 KB | Output is correct |
| 18 | Correct | 1 ms | 348 KB | Output is correct |
| 19 | Correct | 0 ms | 348 KB | Output is correct |
| 20 | Correct | 0 ms | 348 KB | Output is correct |
| 21 | Correct | 29 ms | 5684 KB | Output is correct |
| 22 | Correct | 119 ms | 21972 KB | Output is correct |
| 23 | Correct | 118 ms | 22096 KB | Output is correct |
| 24 | Correct | 152 ms | 22188 KB | Output is correct |
| 25 | Correct | 49 ms | 12112 KB | Output is correct |
| 26 | Correct | 57 ms | 12368 KB | Output is correct |
| 27 | Correct | 113 ms | 22100 KB | Output is correct |
| 28 | Correct | 137 ms | 21976 KB | Output is correct |
| 29 | Correct | 98 ms | 12048 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 348 KB | Output is correct |
| 2 | Correct | 0 ms | 348 KB | Output is correct |
| 3 | Incorrect | 0 ms | 348 KB | Answer gives possible 0 while actual possible 1 |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Incorrect | 0 ms | 348 KB | Answer gives possible 0 while actual possible 1 |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 348 KB | Output is correct |
| 2 | Incorrect | 0 ms | 348 KB | Answer gives possible 0 while actual possible 1 |
| 3 | Halted | 0 ms | 0 KB | - |