oj.uz

Submission #126936

# Submission time Handle Problem Language Result Execution time Memory
126936 2019-07-08T16:15:00 Z mahmoudbadawy Meetings (JOI19_meetings) C++17
7 / 100
 2000 ms 3112 KB 
#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=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(i!=j&&i!=k&&j!=k) ans[i][j][k]=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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 59 ms 3112 KB Wrong Answer [2]
15 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 59 ms 3112 KB Wrong Answer [2]
15 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3020 ms 692 KB Time limit exceeded
2 Halted 0 ms 0 KB -