QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485542#4938. Writing TasksPetroTarnavskyi#Compile Error//C++202.6kb2024-07-20 19:37:202024-07-20 19:37:20

Judging History

你现在查看的是最新测评结果

  • [2024-07-20 19:37:20]
  • 评测
  • [2024-07-20 19:37:20]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

mt19937 rng;

struct Graph
{
	int szL, szR;
	
	vector<VI> g;
	VI mateForR, mateForL, usedL;
	
	void init(int L, int R)
	{
		szL = L, szR = R;
		g.resize(szL);
		mateForL.resize(szL);
		usedL.resize(szL);
		
		mateForR.resize(szR);
	}
	
	void addEdge(int from, int to)
	{
		assert(0 <= from && from < szL);
		assert(0 <= to && to < szR);
		
		g[from].PB(to);
	}
	
	int iter;
	
	bool kuhn(int v)
	{
		if (usedL[v] == iter) return false;
		usedL[v] = iter;
		shuffle(ALL(g[v]), rng);
		for (int to : g[v])
		{
			if (mateForR[to] == -1)
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		for (int to : g[v])
		{
			if (kuhn(mateForR[to]))
			{
				mateForR[to] = v;
				mateForL[v] = to;
				return true;
			}
		}
		return false;
	}
	
	int doKuhn()
	{
		fill(ALL(mateForR), -1);
		fill(ALL(mateForL), -1);
		fill(ALL(usedL), -1);
		
		int res = 0;
		iter = 0;
		while (true)
		{
			iter++;
			bool ok = false;
			FOR (v, 0, szL)
			{
				if (mateForL[v] == -1)
				{
					if (kuhn(v))
					{
						ok = true;
						res++;
					}
				}
			}
			if (!ok)
				break;
		}
		return res;
	}
};

const int N = 200'447;

VI g[N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, c, t;
	cin >> a >> c >> t;
	
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + x - 1);
		}
	}
	FOR (i, 0, a)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[i].PB(a + c + x - 1);
		}
	}
	
	FOR (i, 0, c)
	{
		int l;
		cin >> l;
		FOR (j, 0, l)
		{
			int x;
			cin >> x;
			g[a + i].PB(a + c + x - 1);
		}
	}
	
	map<PII, VI> m;
	
	int cnt = 0;
	
	FOR (i, 0, a)
	{
		set<int> susids;
		for (auto to : g[i])
			susids.insert(to);
		for (auto u : g[i])
		{
			for (auto v : g[u])
			{
				if (!susids.count(v))
					continue;
				m[{i, u}].PB(cnt);
				m[{i, v}].PB(cnt);
				m[{u, u}].PB(cnt);
				cnt++;
			}
		}
	}
	Graph G;
	G.init(cnt, cnt);
	for (auto [p, v] : m)
	{
		assert(SZ(v) <= 2);
		if (SZ(v) == 2)
		{
			G.addEdge(v[0], v[1]);
			G.addEdge(v[1], v[0]);
		}
	}
	cout << cnt - G.doKuhn() / 2 << '\n';
	
	
	
	return 0;
}
123

Details

answer.code:190:1: error: expected unqualified-id before numeric constant
  190 | 123
      | ^~~