Submission #456132

#	Time	Username	Problem	Language	Result	Execution time	Memory
456132		fuad27	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	295 ms	32124 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();
    	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:20: 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:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |       for(int i=1; i<x.s.size(); i++){
      |                    ~^~~~~~~~~~~

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