제출 #650333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650333		esomer	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	212 ms	24016 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;
/*
int n2;
std::vector<std::vector<int>> p;
std::vector<std::vector<int>> b;
bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        cout << message << endl;
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n2, "Invalid number of rows in b");
    for (int i = 0; i < n2; i++) {
        check((int)_b[i].size() == n2, "Invalid number of columns in b");
    }
    b = _b;
}*/

void DFS(int x, vector<int>& num, int curr, int type, vector<vector<int>>& edges){
    if(curr == (int)num.size() - 1){
        if(type == 1) return;
        else{
            edges[num[curr]][x] = 1;
            edges[x][num[curr]] = 1;
            return;
        }
    }
    edges[num[curr]][num[curr + 1]] = 1;
    edges[num[curr + 1]][num[curr]] = 1;
    DFS(x, num, curr + 1, type, edges);
}

int construct(vector<vector<int>> v){
    int n = (int)v[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(v[i][j] == 3) return 0;
        }
    }
    vector<bool> done(n, 0);
    vector<vector<int>> edges(n, vector<int> (n, 0));
    for(int i = 0; i < n; i++){
        if(done[i]) continue;
        vector<int> two;
        vector<int> one = {i};
        set<int> cc;
        cc.insert(i);
        done[i] = 1;
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            if(v[i][j] == 1) {one.push_back(j); cc.insert(j);}
            else if(v[i][j] == 2) {two.push_back(j); cc.insert(j);}
        }
        for(int x : two){
            done[x] = 1;
            for(int j = 0; j < n; j++){
                if(x == j) continue;
                bool good = cc.count(j);
                if(good == false && v[x][j] > 0) return 0;
                //if(good == true && v[x][j] != max(v[i][j], v[i][x])) return 0;
            }
        }
        for(int x : one){
            done[x] = 1;
            for(int j = 0; j < n; j++){
                if(x == j) continue;
                bool good = cc.count(j);
                if(good == false && v[x][j] > 0) return 0;
                if(good == true && v[x][j] != max(v[i][j], v[i][x])) return 0;
            }
        }
        if(two.size() == 0){
            DFS(i, one, 0, 1, edges);
        }else{
            vector<vector<int>> circle;
            circle.push_back(one);
            vector<bool> assigned(two.size(), 0);
            for(int j = 0; j < two.size(); j++){
                if(assigned[j]) continue;
                assigned[j] = 1;
                one.resize(0);
                one.push_back(two[j]);
                for(int q = 0; q < two.size(); q++){
                    if(q == j) continue;
                    if(v[two[j]][two[q]] == 1){
                        if(assigned[q]) return 0;
                        assigned[q] = 1;
                        one.push_back(two[q]);
                    }
                }
                circle.push_back(one);
            }
            if((int)circle.size() < 3) return 0;
            for(auto t : circle){
                DFS(i, t, 0, 1, edges);
            }
            int sz = (int)circle.size();
            for(int j = 0; j < sz; j++){
                edges[circle[j][0]][circle[(j + 1) % sz][0]] = 1;
                edges[circle[(j + 1) % sz][0]][circle[j][0]] = 1;
            }
        }
    }
    build(edges);
    return 1;
}
/*
int main() {
    cin >> n2;

    p.resize(n2);
    for (int i = 0; i < n2; i++) {
        p[i].resize(n2);
    }

    for (int i = 0; i < n2; i++) {
        for (int j = 0; j < n2; j++) {
            cin >> p[i][j];
        }
    }

    int possible = construct(p);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    cout << possible << endl;
    if (possible == 1) {
        for (int i = 0; i < n2; i++) {
            for (int j = 0; j < n2; j++) {
                if (j) {
                    cout << " ";
                }
                cout << b[i][j];
            }
            printf("\n");
        }
    }
}*/

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:92:30: 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 = 0; j < two.size(); j++){
      |                            ~~^~~~~~~~~~~~
supertrees.cpp:97:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                 for(int q = 0; q < two.size(); q++){
      |                                ~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4