답안 #300523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300523	2020-09-17T08:42:25 Z	davitmarg	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	268 ms	26264 KB

supertrees

/*
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 

*/

Compilation message

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: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++)
      |                         ~~^~~~~~~~~~

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	268 ms	26104 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	268 ms	26104 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	11 ms	1408 KB	Output is correct
13	Correct	243 ms	26104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	7 ms	1024 KB	Output is correct
17	Correct	111 ms	16120 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	1 ms	256 KB	Output is correct
20	Correct	65 ms	6904 KB	Output is correct
21	Correct	261 ms	26104 KB	Output is correct
22	Correct	246 ms	26072 KB	Output is correct
23	Correct	262 ms	26104 KB	Output is correct
24	Correct	249 ms	26104 KB	Output is correct
25	Correct	102 ms	16248 KB	Output is correct
26	Correct	100 ms	16120 KB	Output is correct
27	Correct	263 ms	26104 KB	Output is correct
28	Correct	245 ms	26232 KB	Output is correct

Subtask #3

0 / 19.0

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

Subtask #4

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	62 ms	6780 KB	Output is correct
5	Correct	255 ms	26104 KB	Output is correct
6	Correct	247 ms	26204 KB	Output is correct
7	Correct	258 ms	26232 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	62 ms	6780 KB	Output is correct
10	Correct	253 ms	26104 KB	Output is correct
11	Correct	248 ms	26264 KB	Output is correct
12	Correct	257 ms	26104 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	63 ms	6904 KB	Output is correct
17	Correct	249 ms	26104 KB	Output is correct
18	Correct	252 ms	26208 KB	Output is correct
19	Correct	244 ms	26104 KB	Output is correct
20	Correct	248 ms	26204 KB	Output is correct

Subtask #5

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	268 ms	26104 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	11 ms	1408 KB	Output is correct
13	Correct	243 ms	26104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	7 ms	1024 KB	Output is correct
17	Correct	111 ms	16120 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	1 ms	256 KB	Output is correct
20	Correct	65 ms	6904 KB	Output is correct
21	Correct	261 ms	26104 KB	Output is correct
22	Correct	246 ms	26072 KB	Output is correct
23	Correct	262 ms	26104 KB	Output is correct
24	Correct	249 ms	26104 KB	Output is correct
25	Correct	102 ms	16248 KB	Output is correct
26	Correct	100 ms	16120 KB	Output is correct
27	Correct	263 ms	26104 KB	Output is correct
28	Correct	245 ms	26232 KB	Output is correct
29	Correct	1 ms	256 KB	Output is correct
30	Correct	1 ms	288 KB	Output is correct
31	Correct	1 ms	256 KB	Output is correct
32	Incorrect	1 ms	256 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	268 ms	26104 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	11 ms	1408 KB	Output is correct
13	Correct	243 ms	26104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	7 ms	1024 KB	Output is correct
17	Correct	111 ms	16120 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	1 ms	256 KB	Output is correct
20	Correct	65 ms	6904 KB	Output is correct
21	Correct	261 ms	26104 KB	Output is correct
22	Correct	246 ms	26072 KB	Output is correct
23	Correct	262 ms	26104 KB	Output is correct
24	Correct	249 ms	26104 KB	Output is correct
25	Correct	102 ms	16248 KB	Output is correct
26	Correct	100 ms	16120 KB	Output is correct
27	Correct	263 ms	26104 KB	Output is correct
28	Correct	245 ms	26232 KB	Output is correct
29	Correct	1 ms	256 KB	Output is correct
30	Correct	1 ms	288 KB	Output is correct
31	Correct	1 ms	256 KB	Output is correct
32	Incorrect	1 ms	256 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-