oj.uz

답안 #1069979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069979 2024-08-22T10:48:12 Z hasan2006 슈퍼트리 잇기 (IOI20_supertrees) C++17
19 / 100
 154 ms 22212 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];
            vector<int>vv;
            vv.pb(f);
            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];
                    vv.pb(f);
                }
            }
            for(auto to : vv){
                s=  0;
                for(auto to1:vv)
                if(v[to][to1] != 1)
                    return 0;
                for(j = 0; j < n; j++)
                    if(v[to][j] == 1)
                    s++;
                if(s != vv.size())
                    return 0;
            }
        }
        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() && l + r > 0){
            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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(x = 0; x < v1.size(); x++){
      |                    ~~^~~~~~~~~~~
supertrees.cpp:48:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(y = x + 1; y < v1.size(); y++){
      |                            ~~^~~~~~~~~~~
supertrees.cpp:71:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 if(s != vv.size())
      |                    ~~^~~~~~~~~~~~
supertrees.cpp:89:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |             if(v2.size() <= vc.back().fi){
      |                          ^
supertrees.cpp:116:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             if((L > l) || (R > r) || s != v1.size())
      |                                      ~~^~~~~~~~~~~~
supertrees.cpp:27:40: warning: unused variable 'm' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                        ^
supertrees.cpp:27:52: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                                    ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 5 ms 1112 KB Output is correct
9 Correct 112 ms 22048 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1352 KB Output is correct
13 Correct 154 ms 22148 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 856 KB Output is correct
17 Correct 77 ms 12116 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 36 ms 5724 KB Output is correct
22 Correct 115 ms 22160 KB Output is correct
23 Correct 114 ms 22096 KB Output is correct
24 Correct 135 ms 22212 KB Output is correct
25 Correct 66 ms 12116 KB Output is correct
26 Correct 52 ms 12304 KB Output is correct
27 Correct 111 ms 22044 KB Output is correct
28 Correct 138 ms 21980 KB Output is correct
29 Correct 53 ms 12112 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -