oj.uz

Submission #131588

# Submission time Handle Problem Language Result Execution time Memory
131588 2019-07-17T10:06:46 Z MrTEK Meetings (JOI19_meetings) C++14
0 / 100
 309 ms 760 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair <int,int> ii;
 
const int N = 2e3 + 5;
 
vector <int> v;
int mark[N][N];
 
void bridge(int x,int y) {	
	Bridge(min(x,y),max(x,y));
}

int randint(int l, int r) {
  int v = (rand() << 15) ^ rand();
  v %= r - l + 1;
  return v + l;
}
 
void solve(vector <int> v) {
	if (v.size() < 2)
		return;
	if (v.size() == 2) {
		bridge(v[0],v[1]);
		return;
	}
	int rnd = randint(1,v.size()) - 1;
	swap(v[0],v[rnd]);
	for (int i = 1 ; i < v.size() ; i++) {
		if (mark[v[0]][i])
			continue;
		vector <int> nv;
		nv.push_back(i);
		mark[v[0]][i] = 1;
		for (int j = i + 1 ; j < v.size() ; j++)
			if (mark[v[0]][j] == 0) {
				int temp = Query(v[0],v[i],v[j]);
				if (temp != v[0]) {
					mark[v[0]][j] = 1;
					nv.push_back(j);
				}
			}
		vector <int> nv2,vec,vec2;
		for (auto i : nv)
			nv2.push_back(v[i]);
        for (auto j : nv)
            vec.push_back(v[j]);
    	while(vec.size() != 1) {
            vec2.clear();
            for (int i = 0 ; i < vec.size() ; i += 2) {
                if (i + 1 >= vec.size())
                    vec2.push_back(vec[i]);
                else {
                    int temp = Query(v[0],vec[i],vec[i + 1]);
                    if (temp == vec[i])
                        vec2.push_back(vec[i]);
                    if (temp == vec[i + 1])
                        vec2.push_back(vec[i + 1]);
                }
            }
            swap(vec,vec2);
        }
        bridge(vec[0],v[0]);
		solve(nv2);
	}
 
}
 
void Solve(int n) {
	srand(time(NULL));	
	for (int i = 0 ; i < n ; i++)
		v.push_back(i);
	solve(v);
}

Compilation message

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < v.size() ; i++) {
                   ~~^~~~~~~~~~
meetings.cpp:38:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1 ; j < v.size() ; j++)
                        ~~^~~~~~~~~~
meetings.cpp:53:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0 ; i < vec.size() ; i += 2) {
                              ~~^~~~~~~~~~~~
meetings.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (i + 1 >= vec.size())
                     ~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 676 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -