Submission #927618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927618	2024-02-15T07:26:30 Z	MrDeboo	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

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

static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}
vector<int>vct[1000][2];
vector<vector<int>>ans;
vector<vector<int>>P;
int slv(vector<int>v){
    cerr<<'f';
	for(auto &i:v){
		for(auto &w:v){
			if(!p[i][w])return 0;
		}
	}
	vector<int>V;
	vector<bool>vis(p.size());
	for(int i=0;i<v.size();i++){
		if(vis[i])continue;
		int I=i;
		for(int w=0;w<v.size();w++){
			if(P[v[i]][v[w]]==1&&!vis[w]&&i!=w){
				bool bl=1;
				for(int j=0;j<v.size();j++){
					if(j==i||j==w)continue;
					if(P[v[j]][v[i]]!=P[v[j]][v[w]])bl=0;
				}
				if(bl){
					vis[w]=1;
					ans[v[I]][v[w]]=1;
					ans[v[w]][v[I]]=1;
					I=w;
				}
			}
		}
		V.push_back(v[i]);
		vis[i]=1;
	}
	v=V;
	for(int i=0;i<v.size();i++){
		for(int w=i+1;w<v.size();w++){
			if(P[v[i]][v[w]]!=2)return 0;
		}
	}
	if(v.size()>1){
        if(v.size()==2)return 0;
		for(int i=0;i<v.size();i++){
			ans[v[i]][v[(i+1)%v.size()]]=1;
			ans[v[(i+1)%v.size()]][v[i]]=1;
		}
	}
	return 1;
}
int construct(std::vector<std::vector<int>> p){
	for(auto &i:p){
		for(auto &w:i){
			if(w>2)return 0;
		}
	}
	for(auto &i:p)P.push_back(i);
	int n=p.size();
	for(int i=0;i<n;i++){
		for(int w=0;w<n;w++){
			if(i==w)continue;
			vct[i][p[i][w]-1].push_back(w);
		}
	}
	for(int i=0;i<n;i++){
		vector<int>v(n);
		ans.push_back(v);
	}
	vector<bool>vis(n);
	for(int i=0;i<n;i++){
		for(int w=0;w<n;w++){
			if(vis[i]||vis[w]||i==w)continue;
			if(p[i][w]){
				deque<int>dq={i};
				vis[i]=1;
				vector<int>vc;
				while(dq.size()){
					int a=dq.front();
					vc.push_back(a);
					dq.pop_front();
					for(auto &j:vct[a][1]){
						if(!vis[j]){
							vis[j]=1;
							dq.push_back(j);
						}
					}
					for(auto &j:vct[a][0]){
						if(!vis[j]){
							vis[j]=1;
							dq.push_back(j);
						}
					}
				}
				if(!slv(vc))return 0;
			}
		}
	}
	build(ans);
	return 1;
}
int main() {
    assert(scanf("%d", &n) == 1);

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);

    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");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}

Compilation message

supertrees.cpp: In function 'int slv(std::vector<int>)':
supertrees.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
supertrees.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int w=0;w<v.size();w++){
      |               ~^~~~~~~~~
supertrees.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j=0;j<v.size();j++){
      |                 ~^~~~~~~~~
supertrees.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
supertrees.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int w=i+1;w<v.size();w++){
      |                 ~^~~~~~~~~
supertrees.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i=0;i<v.size();i++){
      |               ~^~~~~~~~~
/usr/bin/ld: /tmp/ccQmxPq5.o: in function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x260): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'; /tmp/ccUaxim5.o:supertrees.cpp:(.text+0x1d0): first defined here
/usr/bin/ld: /tmp/ccQmxPq5.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUaxim5.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status