Submission #456235

#	Time	Username	Problem	Language	Result	Execution time	Memory
456235		fuad27	Connecting Supertrees (IOI20_supertrees)	C++14	75 / 100	288 ms	30212 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] == 1)check = 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:24: 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:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int i = 1; i < div.size(); ++i)
      |                             ~~^~~~~~~~~~~~
supertrees.cpp:90:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for (int i = 1; i < vv.size(); ++i)
      |                                 ~~^~~~~~~~~~~
supertrees.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |           for(int i=1; i<x.s.size(); i++){
      |                        ~^~~~~~~~~~~

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