Submission #543535

#	Time	Username	Problem	Language	Result	Execution time	Memory
543535		fuad27	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1094 ms	10136 KiB

supertrees

            #include "supertrees.h"
    #include<bits/stdc++.h>
    using namespace std;
#define s second
    int visited[2000];
    vector<vector<int> > adjlist;
    int coun=1;
    void dfs(int s){
	visited[s]=coun;
	for(int i=0; i<adjlist[s].size(); i++){
		int v=adjlist[s][i];
		if(visited[v]==0)
			dfs(v);
	}
    }
    int construct(vector<vector<int> > p) {
	int n = p.size();
	bool check = true;
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<n;j++) {
			if(i == j)continue;
			if(p[i][j] == 3 or p[i][j] != p[j][i])return 0;
			if(p[i][j] == 1)check = false;
		}
	}
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<n;j++) {
			for(int k = 0;k<n;k++) {
				if(k == i or j == k or i == j)continue;
				if(p[i][j] == 1 and p[j][k] == 1 and p[i][k]!=1)return false;
			}
		}
	}
	if(!check) {

		    vector< vector< int > > ans(n, vector< int >(n));
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
	if (p[i][j] == 3)
	    return 0;

vector< int > siv(n, false);

vector< int > vis(n, false);
for (int i = 0; i < n; ++i)
    if (not vis[i])
    {
	vector< int > sub;
	for (int j = 0; j < n; ++j)
	    if (p[i][j] and not vis[j])
		sub.push_back(j);
	    else if (p[i][j] and vis[j]) return 0;

	for (int a : sub)
	    vis[a] = true;

	for (int a : sub)
	    for (int j = 0; j < n; ++j)
		if (not vis[j] and p[a][j])
		    return 0;

	for (int a : sub)
	    for (int b : sub)
		if (not p[a][b])
		    return 0;


	vector< vector< int > > div;
	for (int a : sub)
	    if (not siv[a])
	    {
		div.push_back(vector< int >());
		for (int b : sub)
		    if (p[a][b] == 1 and not siv[b])
			div.back().push_back(b);
		    else if (p[a][b] == 1 and siv[b]) return 0;

		for (int a : div.back())
		    siv[a] = true;

		for (int a : div.back())
		    for (int b : sub)
			if (not siv[b] and p[a][b] == 1)
			    return 0;

		for (int a : div.back())
		    for (int b : div.back())
			if (p[a][b] != 1)
			    return 0;
	    }

	for (int i = 1; i < div.size(); ++i)
	    ans[div[i - 1][0]][div[i][0]] = ans[div[i][0]][div[i - 1][0]] = 1;

	if (div.size() > 1)
	    ans[div.back()[0]][div.front()[0]] = ans[div.front()[0]][div.back()[0]] = 1;

	for (const auto& vv : div)
	    for (int i = 1; i < vv.size(); ++i)
		ans[vv[i]][vv[i - 1]] = ans[vv[i - 1]][vv[i]] = 1;
    }

build(ans);
return 1;
	}
	adjlist.assign(n+1, vector<int>());
	bool is=false;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(p[i][j] && i!=j){
				adjlist[i].push_back(j);
				adjlist[j].push_back(i);
			}
			if(p[i][j]==2)
				is=true;
		}
	}
	for(int i=0; i<n; i++){
		if(visited[i]==0){
			dfs(i);
			coun++;
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(visited[i]==visited[j] && p[i][j]==0)
				return 0;
		}
	}
	vector<vector<int> > answer;
	answer.assign(n, vector<int>());
	for(int i=0; i<n; i++)
		answer[i].assign(n, 0);
	map<int, vector<int> > mp;
	for(int i=0; i<n; i++)
		mp[visited[i]].push_back(i);
	for(auto x:mp){
		for(int i=1; i<x.s.size(); i++){
			answer[x.s[i-1]][x.s[i]]=1;
			answer[x.s[i]][x.s[i-1]]=1;
		}
		if(is){
			if(x.s.size()==1)
				continue;
			if(x.s.size()==2)
				return 0;
			answer[x.s[0]][x.s[x.s.size()-1]]=1;
			answer[x.s[x.s.size()-1]][x.s[0]]=1;
		}
	}
	build(answer);
	return 1;
    }

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i=0; i<adjlist[s].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 1; i < div.size(); ++i)
      |                  ~~^~~~~~~~~~~~
supertrees.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |      for (int i = 1; i < vv.size(); ++i)
      |                      ~~^~~~~~~~~~~
supertrees.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i=1; i<x.s.size(); i++){
      |                ~^~~~~~~~~~~

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