Submission #311818

#	Time	Username	Problem	Language	Result	Execution time	Memory
311818		aryan12	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	314 ms	22280 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

/*void build(vector<vector<int> > ans) {
    for(int i = 0; i < ans.size(); i++) {
        for(int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}*/

int Task(vector<vector<int> > p) {
    int f0 = 0, f1 = 0, f2 = 0, f3 = 0;
    for(int i = 0; i < p.size(); i++) {
        for(int j = 0; j < p[i].size(); j++) {
            if(p[i][j] == 0)
                f0++;
            if(p[i][j] == 1)
                f1++;
            if(p[i][j] == 2)
                f2++;
            if(p[i][j] == 3)
                f3++;
        }
    }
    f1 -= p.size();
    if(f3 != 0)
        return 6;
    if(f1 == 0 && f0 == 0 && f2 == 0 && f3 == 0)
        return 1;
    if(f1 != 0 && f0 == 0 && f2 == 0 && f3 == 0)
        return 1;
    if(f1 != 0 && f0 != 0 && f2 == 0 && f3 == 0)
        return 2;
    if(f1 == 0 && f0 != 0 && f2 == 0 && f3 == 0)
        return 2;
    if(f1 == 0 && f0 == 0 && f2 != 0 && f3 == 0)
        return 3;
    if(f1 == 0 && f0 != 0 && f2 != 0 && f3 == 0)
        return 3;
    return 4;
}

int construct(vector<vector<int> > p) {
	int n = p.size();
	int x = Task(p);
	vector<vector<int> > g;
	for(int i = 0; i < n; i++) {
        vector<int> ans;
        for(int j = 0; j < n; j++) {
            ans.push_back(0);
        }
        g.push_back(ans);
	}
	//cout << x << endl;
	if(x == 1) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0)
                    g[i][j] = 0;
                else if(i == 0 || j == 0)
                    g[i][j] = 1;
            }
        }
        build(g);
        return 1;
	}
	if(x == 2) {
        bool vis[n];
        for(int i = 0; i < n; i++) {
            vis[i] = false;
        }
        for(int i = 0; i < n; i++) {
            set<int> Component;
            if(!vis[i]) {
                vis[i] = true;
                for(int j = 0; j < n; j++) {
                    if(p[i][j] == 1) {
                        Component.insert(j);
                        vis[j] = true;
                    }
                }
                int lol = 0;
                for(auto j: Component) {
                    for(int k = 0; k < n; k++) {
                        if(Component.count(k) && p[j][k] != 1)
                            return 0;
                        if(!Component.count(k) && p[j][k] == 1)
                            return 0;
                    }
                }
                for(auto j: Component) {
                    g[i][j] = 1;
                    g[j][i] = 1;
                }
                g[i][i] = 0;
            }
        }
        build(g);
        return 1;
	}
	if(x == 3) {
        //cout << "G" << endl;
        set<int> vis;
        for(int i = 0; i < n; i++) {
            vector<int> Component;
            set<int> comp;
            if(!vis.count(i)) {
                //cout << "Cuacemole" << endl;
                Component.push_back(i);
                comp.insert(i);
                vis.insert(i);
                for(int j = 0; j < p[i].size(); j++) {
                    if(p[i][j] == 2) {
                        Component.push_back(j);
                        comp.insert(j);
                        if(vis.count(j))
                            return 0;
                        vis.insert(j);
                    }
                }
                //cout << "Random" << endl;
                for(auto j: comp) {
                    for(int k = 0; k < n; k++) {
                        if(comp.count(k) && p[j][k] != 2) {
                            if(j != k)
                                return 0;
                        }
                        if(!comp.count(k) && p[j][k] == 2)
                            return 0;
                    }
                }
                //cout << "Dance for me" << endl;
            }
            //cout << "Raikonen " << Component.size() << endl;
            if(Component.size() != 0) {
                for(int i = 0; i < Component.size() - 1; i++) {
                    g[Component[i]][Component[i + 1]]++;
                }
                //cout << "Vettel" << endl;
                g[Component[Component.size() - 1]][Component[0]]++;
                if(Component.size() == 2) {
                    return 0;
                }
            }
            Component.clear();
            comp.clear();
        }
        build(g);
        return 1;
	}
	return 0;
}

/*int main() {
    vector<vector<int> > p;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        vector<int> q;
        for(int j = 0; j < n; j++) {
            int x;
            cin >> x;
            q.push_back(x);
        }
        p.push_back(q);
    }
    cout << construct(p) << endl;
}*/

Compilation message (stderr)

supertrees.cpp: In function 'int Task(std::vector<std::vector<int> >)':
supertrees.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
supertrees.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int j = 0; j < p[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:85:21: warning: unused variable 'lol' [-Wunused-variable]
   85 |                 int lol = 0;
      |                     ^~~
supertrees.cpp:115:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 for(int j = 0; j < p[i].size(); j++) {
      |                                ~~^~~~~~~~~~~~~
supertrees.cpp:139:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                 for(int i = 0; i < Component.size() - 1; i++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~

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