Submission #931556

#	Time	Username	Problem	Language	Result	Execution time	Memory
931556		nguyentunglam	Simurgh (IOI17_simurgh)	C++17	Compilation error	0 ms	0 KiB

simurgh

#include "simurgh.h"
#include "simurgh.cpp"

#include <cstdio>
#include <cassert>
#include <vector>
#include <cstdlib>
#include <string>

using namespace std;

static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;

static void wrong_answer() {
	printf("NO\n");
	assert(0);
	exit(0);
}

static bool is_valid(const vector<int>& r) {
//  for(auto j : r) cout << j << " "; cout << endl;
	if(int(r.size()) != n - 1)
		return false;

	for(int i = 0; i < n - 1; i++)
		if (r[i] < 0 || r[i] >= m)
			return false;

	return true;
}

struct dsu {
  vector<int> lab;

  void init (int n) {
    lab.resize(n + 3);
    for(int i = 0; i <= n; i++) lab[i] = -1;
  }

  int root(int v) {
    return lab[v] < 0 ? v : lab[v] = root(lab[v]);
  }

  bool join(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
  }
};

static int _count_common_roads_internal(const vector<int>& r) {
	if(!is_valid(r))
		wrong_answer();
//
//  dsu tmp;
//  tmp.init(n);
//
//  for(auto &j : r) {
//    assert(tmp.join(u[j], v[j]));
//  }

	int common = 0;
	for(int i = 0; i < n - 1; i++) {
		bool is_common = goal[r[i]];
		if (is_common)
			common++;
	}

	return common;
}

int count_common_roads(const vector<int>& r) {
	q++;
	if(q > MAXQ)
		wrong_answer();

	return _count_common_roads_internal(r);
}

int main() {
	freopen ("task.inp", "r", stdin);
	freopen ("task.out", "w", stdout);
	assert(2 == scanf("%d %d", &n, &m));

	u.resize(m);
	v.resize(m);

	for(int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	goal.resize(m, false);

	for(int i = 0; i < n - 1; i++) {
		int id;
		assert(1 == scanf("%d", &id));
		goal[id] = true;
	}

	vector<int> res = find_roads(n, u, v);

	if(_count_common_roads_internal(res) != n - 1)
		wrong_answer();

	printf("YES\n");

	return 0;
}

Compilation message (stderr)

simurgh.cpp:2:10: fatal error: simurgh.cpp: No such file or directory
    2 | #include "simurgh.cpp"
      |          ^~~~~~~~~~~~~
compilation terminated.