Submission #126937

#	Time	Username	Problem	Language	Result	Execution time	Memory
126937		mahmoudbadawy	Meetings (JOI19_meetings)	C++17	17 / 100	393 ms	108628 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

const int N=305;

int ans[N][N][N];
vector<int> adj[N];

void solve(int root,vector<int> cur)
{
	int vid[N];
	vector<int> v[N];
	int cursz=1;
	for(int i=0;i<cur.size();i++)
	{
		for(int j=i+1;j<cur.size();j++)
		{
			int x=cur[i],y=cur[j];
			if(ans[root][x][y]==root) continue;
			if(vid[x]==0&&vid[y]==0)
			{
				vid[x]=vid[y]=cursz++;
				v[cursz-1].push_back(x);
				v[cursz-1].push_back(y);
			}
			if(!vid[x])
			{
				v[vid[y]].push_back(x);
				vid[x]=vid[y];
			}
			if(!vid[y])
			{
				v[vid[x]].push_back(y);
				vid[y]=vid[x];
			}
		}
	}
	for(int i:cur)
	{
		if(!vid[i])
		{
			adj[i].push_back(root);
			adj[root].push_back(i);
		}
	}
	for(int i=1;i<cursz;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			int sz=0;
			for(int k=0;k<v[i].size();k++)
			{
				if(k==j) continue;
				sz+=(ans[root][v[i][j]][v[i][k]]==v[i][j]);
			}
			if(sz==v[i].size()-1)
			{
				adj[root].push_back(v[i][j]);
				adj[v[i][j]].push_back(root);
				int nroot=v[i][j];
				v[i].erase(v[i].begin()+j);
				if(v[i].size())
					solve(nroot,v[i]);
				break;
			}
		}
	}
}

void Solve(int n) {
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			for(int k=j+1;k<n;k++)
			{
				ans[i][j][k]=ans[i][k][j]=ans[j][i][k]=ans[j][k][i]=ans[k][i][j]=ans[k][j][i]=Query(i,j,k);
			}
	vector<int> v;
	for(int i=1;i<n;i++) v.push_back(i);
	solve(0,v);
	for(int i=0;i<n;i++)
		for(int j:adj[i])
			if(i<j)
				Bridge(i,j);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>)':
meetings.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cur.size();i++)
              ~^~~~~~~~~~~
meetings.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<cur.size();j++)
                 ~^~~~~~~~~~~
meetings.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v[i].size();j++)
               ~^~~~~~~~~~~~
meetings.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<v[i].size();k++)
                ~^~~~~~~~~~~~
meetings.cpp:58:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(sz==v[i].size()-1)
       ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71