QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#578333	#9319. Bull Farm	yzj123	Compile Error	/	/	C++14	9.3kb	2024-09-20 18:20:12	2024-09-20 18:20:13

Judging History

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

[2024-09-20 18:20:13]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2024-09-20 18:20:12]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int read()
{
	int res = 0, bj = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') bj = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * bj;
}
const int MAXN = 2005, MAXM = 1e6 + 5;
int tt, T;
int n, m, q; //n个牛棚, m个按钮 
char s[MAXM];
struct Que {
	int a, b, c;
	int ans;
	int id;
}que[MAXM]; 
int t[MAXN][MAXN];
bitset<MAXN> f[MAXN];
struct Edge {
	int x, y;
}e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
//e1保存的原图的边 
vector<int> g[MAXN]; //染色图的边 
int cnt1, cnt2; 
vector<int> pos[MAXN]; //第i种染色对应的点 
int in[MAXN]; //节点入度 
int dfn[MAXN], low[MAXN], inx;
int stk[MAXN], top;
int vis[MAXN];
int scc, col[MAXN];
void tarjan(int u)
{
	dfn[u] = low[u] = ++inx;
	stk[++top] = u;
	vis[u] = 1;
	for (int v : g[u])
	{
		if (!dfn[v]) 
		{
			tarjan(v);
			low[u] = min(low[u], low[v]); 
		}
		else if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u])
	{
		scc++;
		int t;
		do {
			t = stk[top--];
			vis[t] = 0;
			for (int x : pos[t]) col[x] = scc;
		} while (t != u);
	}
}
void work(int K) //第K个按钮 
{
	 
	//重置e1数组 	
	for (int i = 1; i <= n; i++) in[i] = 0;
	for (int i = 1; i <= n; i++) in[t[K][i]]++;
	for (int i = 1; i <= n; i++) 
		if (in[i] >= 3) return; //入度>=3不符合条件 
	int sum2 = 0, p = 0; //入度为2的节点个数 
	for (int i = 1; i <= n; i++)
		if (in[i] == 2) sum2++, p = i;
	if (sum2 >= 2) return;
	for (int i = 1; i <= cnt2; i++) e1[i] = e2[i];
	cnt1 = cnt2;
	cnt2 = 0;
	if (sum2 == 1)
	{
		int x1 = 0, x2 = 0, y;
		for (int i = 1; i <= n; i++) 
			if (t[K][i] == p) x1 = i;
		for (int i = 1; i <= n; i++) 
			if (t[K][i] == p && i != x1) x2 = i;
		for (int i = 1; i <= n; i++) 
			if (in[i] == 0) y = i;
		e1[++cnt1] = (Edge){x1, y}; 
		e1[++cnt1] = (Edge){x2, y}; 
	}
	else 
	{
		for (int i = 1; i <= n; i++)
		{
			int x = i, y = t[K][i];
			e1[++cnt1] = (Edge){x, y};
		}
	}
	
	int last_scc = scc;
	for (int i = 1; i <= last_scc; i++) g[i].clear(); 
	for (int i = 1; i <= cnt1; i++) 
	{
		int x = e1[i].x, y = e1[i].y;
		if (col[x] != col[y]) 
		{
			g[col[x]].push_back(col[y]);
		}
	}
	
	//tarjan清空 
	for (int i = 1; i <= last_scc; i++)
	{
		dfn[i] = low[i] = 0;
		vis[i] = 0;
		col[i] = 0;
	}
	inx = top = scc = 0;
	
	for (int i = 1; i <= last_scc; i++) 
		if (!dfn[i]) tarjan(i);
	
	//更新pos数组 
	for (int i = 1; i <= last_scc; i++) pos[i].clear();
	for (int i = 1; i <= n; i++) pos[col[i]].push_back(i);
	
	//更新g数组为topsort数组 
	for (int i = 1; i <= last_scc; i++) g[i].clear();
	map<pair<int, int>, int> ma;
	for (int i = 1; i <= cnt1; i++)
	{
		int x = e1[i].x, y = e1[i].y;
		if (col[x] != col[y]) 
		{
			if (ma[make_pair(col[x], col[y])] == 1) continue; 
			g[col[y]].push_back(col[x]);
			ma[make_pair(col[x], col[y])] = 1;
			e2[++cnt2] = (Edge){x, y};
		}
	} 
	for (int i = 1; i <= scc; i++) in[i] = 0; //in数组清空 
	for (int i = 1; i <= scc; i++) f[i].reset();
	for (int u = 1; u <= scc; u++)
		for (int v : g[u]) in[v]++;
	queue<int> q;
	for (int i = 1; i <= scc; i++)
	{
		f[i].set(i);
		if (in[i] == 0) q.push(i);
	} 
	while (q.size())
	{
		int u = q.front();
		q.pop();
		for (int v : g[u])
		{
			f[v] |= f[u];
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
}
void solve()
{
	n = read(), m = read(), q = read();
	for (int i = 1; i <= m; i++)
	{
		scanf("%s", s + 1);
		int len = strlen(s + 1); 
		for (int j = 1; j <= len; j += 2) 
		{
			int x = s[j] - 48, y = s[j + 1] - 48;
			t[i][(j + 1) / 2] = x * 50 + y; 
		} 
	}
	for (int i = 1; i <= q; i++)
	{
		que[i].id = i;
		scanf("%s", s + 1);
		int x, y;
		x = s[1] - 48, y = s[2] - 48;
		que[i].a = x * 50 + y;
		x = s[3] - 48, y = s[4] - 48;
		que[i].b = x * 50 + y;
		x = s[5] - 48, y = s[6] - 48;
		que[i].c = x * 50 + y;
	}
	sort(que + 1, que + q + 1, [](Que A, Que B) {
		return A.c < B.c;
	});
	scc = n;
	for (int i = 1; i <= n; i++) pos[i].clear();
	for (int i = 1; i <= n; i++) 
	{
		pos[i].push_back(i);
		col[i] = i;
		f[i].reset(); //记得重置f数组！！！ 
		f[i].set(i);
	}	
	cnt1 = cnt2 = 0;
	int j = 1;
	for (int i = 1; i <= q; i++)
	{
		while (j <= que[i].c) work(j), j++;
		int a = que[i].a, b = que[i].b;
		que[i].ans = f[col[a]][col[b]];
	}
	sort(que + 1, que + q + 1, [](Que A, Que B) {
		return A.id < B.id;	
	});
	for (int i = 1; i <= q; i++) cout << que[i].ans;
	cout << "\n";
}
int main() 
{
	int tt = read();
	while (tt--) solve();
	return 0;
} #include <bits/stdc++.h>
using namespace std;
int read()
{
	int res = 0, bj = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') bj = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * bj;
}
const int MAXN = 2005, MAXM = 1e6 + 5;
int tt, T;
int n, m, q; //n个牛棚, m个按钮 
char s[MAXM];
struct Que {
	int a, b, c;
	int ans;
	int id;
}que[MAXM]; 
int t[MAXN][MAXN];
bitset<MAXN> f[MAXN];
struct Edge {
	int x, y;
}e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
//e1保存的原图的边 
vector<int> g[MAXN]; //染色图的边 
int cnt1, cnt2; 
vector<int> pos[MAXN]; //第i种染色对应的点 
int in[MAXN]; //节点入度 
int dfn[MAXN], low[MAXN], inx;
int stk[MAXN], top;
int vis[MAXN];
int scc, col[MAXN];
void tarjan(int u)
{
	dfn[u] = low[u] = ++inx;
	stk[++top] = u;
	vis[u] = 1;
	for (int v : g[u])
	{
		if (!dfn[v]) 
		{
			tarjan(v);
			low[u] = min(low[u], low[v]); 
		}
		else if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u])
	{
		scc++;
		int t;
		do {
			t = stk[top--];
			vis[t] = 0;
			for (int x : pos[t]) col[x] = scc;
		} while (t != u);
	}
}
void work(int K) //第K个按钮 
{
	 
	//重置e1数组 	
	for (int i = 1; i <= n; i++) in[i] = 0;
	for (int i = 1; i <= n; i++) in[t[K][i]]++;
	for (int i = 1; i <= n; i++) 
		if (in[i] >= 3) return; //入度>=3不符合条件 
	int sum2 = 0, p = 0; //入度为2的节点个数 
	for (int i = 1; i <= n; i++)
		if (in[i] == 2) sum2++, p = i;
	if (sum2 >= 2) return;
	for (int i = 1; i <= cnt2; i++) e1[i] = e2[i];
	cnt1 = cnt2;
	cnt2 = 0;
	if (sum2 == 1)
	{
		int x1 = 0, x2 = 0, y;
		for (int i = 1; i <= n; i++) 
			if (t[K][i] == p) x1 = i;
		for (int i = 1; i <= n; i++) 
			if (t[K][i] == p && i != x1) x2 = i;
		for (int i = 1; i <= n; i++) 
			if (in[i] == 0) y = i;
		e1[++cnt1] = (Edge){x1, y}; 
		e1[++cnt1] = (Edge){x2, y}; 
	}
	else 
	{
		for (int i = 1; i <= n; i++)
		{
			int x = i, y = t[K][i];
			e1[++cnt1] = (Edge){x, y};
		}
	}
	
	int last_scc = scc;
	for (int i = 1; i <= last_scc; i++) g[i].clear(); 
	for (int i = 1; i <= cnt1; i++) 
	{
		int x = e1[i].x, y = e1[i].y;
		if (col[x] != col[y]) 
		{
			g[col[x]].push_back(col[y]);
		}
	}
	
	//tarjan清空 
	for (int i = 1; i <= last_scc; i++)
	{
		dfn[i] = low[i] = 0;
		vis[i] = 0;
		col[i] = 0;
	}
	inx = top = scc = 0;
	
	for (int i = 1; i <= last_scc; i++) 
		if (!dfn[i]) tarjan(i);
	
	//更新pos数组 
	for (int i = 1; i <= last_scc; i++) pos[i].clear();
	for (int i = 1; i <= n; i++) pos[col[i]].push_back(i);
	
	//更新g数组为topsort数组 
	for (int i = 1; i <= last_scc; i++) g[i].clear();
	map<pair<int, int>, int> ma;
	for (int i = 1; i <= cnt1; i++)
	{
		int x = e1[i].x, y = e1[i].y;
		if (col[x] != col[y]) 
		{
			if (ma[make_pair(col[x], col[y])] == 1) continue; 
			g[col[y]].push_back(col[x]);
			ma[make_pair(col[x], col[y])] = 1;
			e2[++cnt2] = (Edge){x, y};
		}
	} 
	for (int i = 1; i <= scc; i++) in[i] = 0; //in数组清空 
	for (int i = 1; i <= scc; i++) f[i].reset();
	for (int u = 1; u <= scc; u++)
		for (int v : g[u]) in[v]++;
	queue<int> q;
	for (int i = 1; i <= scc; i++)
	{
		f[i].set(i);
		if (in[i] == 0) q.push(i);
	} 
	while (q.size())
	{
		int u = q.front();
		q.pop();
		for (int v : g[u])
		{
			f[v] |= f[u];
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
}
void solve()
{
	n = read(), m = read(), q = read();
	for (int i = 1; i <= m; i++)
	{
		scanf("%s", s + 1);
		int len = strlen(s + 1); 
		for (int j = 1; j <= len; j += 2) 
		{
			int x = s[j] - 48, y = s[j + 1] - 48;
			t[i][(j + 1) / 2] = x * 50 + y; 
		} 
	}
	for (int i = 1; i <= q; i++)
	{
		que[i].id = i;
		scanf("%s", s + 1);
		int x, y;
		x = s[1] - 48, y = s[2] - 48;
		que[i].a = x * 50 + y;
		x = s[3] - 48, y = s[4] - 48;
		que[i].b = x * 50 + y;
		x = s[5] - 48, y = s[6] - 48;
		que[i].c = x * 50 + y;
	}
	sort(que + 1, que + q + 1, [](Que A, Que B) {
		return A.c < B.c;
	});
	scc = n;
	for (int i = 1; i <= n; i++) pos[i].clear();
	for (int i = 1; i <= n; i++) 
	{
		pos[i].push_back(i);
		col[i] = i;
		f[i].reset(); //记得重置f数组！！！ 
		f[i].set(i);
	}	
	cnt1 = cnt2 = 0;
	int j = 1;
	for (int i = 1; i <= q; i++)
	{
		while (j <= que[i].c) work(j), j++;
		int a = que[i].a, b = que[i].b;
		que[i].ans = f[col[a]][col[b]];
	}
	sort(que + 1, que + q + 1, [](Que A, Que B) {
		return A.id < B.id;	
	});
	for (int i = 1; i <= q; i++) cout << que[i].ans;
	cout << "\n";
}
int main() 
{
	int tt = read();
	while (tt--) solve();
	return 0;
}

Source code, Language: C++14

Details

answer.code:220:3: error: stray ‘#’ in program
  220 | } #include <bits/stdc++.h>
      |   ^
answer.code:220:4: error: ‘include’ does not name a type
  220 | } #include <bits/stdc++.h>
      |    ^~~~~~~
answer.code:222:5: error: redefinition of ‘int read()’
  222 | int read()
      |     ^~~~
answer.code:3:5: note: ‘int read()’ previously defined here
    3 | int read()
      |     ^~~~
answer.code:236:11: error: redefinition of ‘const int MAXN’
  236 | const int MAXN = 2005, MAXM = 1e6 + 5;
      |           ^~~~
answer.code:17:11: note: ‘const int MAXN’ previously defined here
   17 | const int MAXN = 2005, MAXM = 1e6 + 5;
      |           ^~~~
answer.code:236:24: error: redefinition of ‘const int MAXM’
  236 | const int MAXN = 2005, MAXM = 1e6 + 5;
      |                        ^~~~
answer.code:17:24: note: ‘const int MAXM’ previously defined here
   17 | const int MAXN = 2005, MAXM = 1e6 + 5;
      |                        ^~~~
answer.code:237:5: error: redefinition of ‘int tt’
  237 | int tt, T;
      |     ^~
answer.code:18:5: note: ‘int tt’ previously declared here
   18 | int tt, T;
      |     ^~
answer.code:237:9: error: redefinition of ‘int T’
  237 | int tt, T;
      |         ^
answer.code:18:9: note: ‘int T’ previously declared here
   18 | int tt, T;
      |         ^
answer.code:238:5: error: redefinition of ‘int n’
  238 | int n, m, q; //n个牛棚, m个按钮
      |     ^
answer.code:19:5: note: ‘int n’ previously declared here
   19 | int n, m, q; //n个牛棚, m个按钮
      |     ^
answer.code:238:8: error: redefinition of ‘int m’
  238 | int n, m, q; //n个牛棚, m个按钮
      |        ^
answer.code:19:8: note: ‘int m’ previously declared here
   19 | int n, m, q; //n个牛棚, m个按钮
      |        ^
answer.code:238:11: error: redefinition of ‘int q’
  238 | int n, m, q; //n个牛棚, m个按钮
      |           ^
answer.code:19:11: note: ‘int q’ previously declared here
   19 | int n, m, q; //n个牛棚, m个按钮
      |           ^
answer.code:239:6: error: redefinition of ‘char s [1000005]’
  239 | char s[MAXM];
      |      ^
answer.code:20:6: note: ‘char s [1000005]’ previously declared here
   20 | char s[MAXM];
      |      ^
answer.code:240:8: error: redefinition of ‘struct Que’
  240 | struct Que {
      |        ^~~
answer.code:21:8: note: previous definition of ‘struct Que’
   21 | struct Que {
      |        ^~~
answer.code:244:2: error: conflicting declaration ‘int que [1000005]’
  244 | }que[MAXM];
      |  ^~~
answer.code:25:2: note: previous declaration as ‘Que que [1000005]’
   25 | }que[MAXM];
      |  ^~~
answer.code:245:5: error: redefinition of ‘int t [2005][2005]’
  245 | int t[MAXN][MAXN];
      |     ^
answer.code:26:5: note: ‘int t [2005][2005]’ previously declared here
   26 | int t[MAXN][MAXN];
      |     ^
answer.code:246:14: error: redefinition of ‘std::bitset<2005> f [2005]’
  246 | bitset<MAXN> f[MAXN];
      |              ^
answer.code:27:14: note: ‘std::bitset<2005> f [2005]’ previously defined here
   27 | bitset<MAXN> f[MAXN];
      |              ^
answer.code:247:8: error: redefinition of ‘struct Edge’
  247 | struct Edge {
      |        ^~~~
answer.code:28:8: note: previous definition of ‘struct Edge’
   28 | struct Edge {
      |        ^~~~
answer.code:249:2: error: conflicting declaration ‘int e1 [4020025]’
  249 | }e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
      |  ^~
answer.code:30:2: note: previous declaration as ‘Edge e1 [4020025]’
   30 | }e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
      |  ^~
answer.code:249:19: error: conflicting declaration ‘int e2 [4020025]’
  249 | }e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
      |                   ^~
answer.code:30:19: note: previous declaration as ‘Edge e2 [4020025]’
   30 | }e1[MAXN * MAXN], e2[MAXN * MAXN]; //e2是temp数组
      |                   ^~
answer.code:251:13: error: redefinition of ‘std::vector<int> g [2005]’
  251 | vector<int> g[MAXN]; //染色图的边
      |             ^
answer.code:32:13: note: ‘std::vector<int> g [2005]’ previously declared here
   32 | vector<int> g[MAXN]; //染色图的边
      |             ^
answer.code:252:5: error: redefinition of ‘int cnt1’
  252 | int cnt1, cnt2;
      |     ^~~~
answer.code:33:5: note: ‘int cnt1’ previously declared here
   33 | int cnt1, cnt2;
      |     ^~~~
answer.code:252:11: error: redefinition of ‘int cnt2’
  252 | int cnt1, cnt2;
      |           ^~~~
answer.code:33:11: note: ‘int cnt2’ previously declared here
   33 | int cnt1, cnt2;
      |           ^~~~
answer.code:253:13: error: redefinition of ‘std::vector<int> pos [2005]’
  253 | vector<int> pos[MAXN]; //第i种染色对应的点
      |             ^~~
answer.code:34:13: note: ‘std::vector<int> pos [2005]’ previously declared here
   34 | vector<int> pos[MAXN]; //第i种染色对应的点
      |             ^~~
answer.code:254:5: error: redefinition of ‘int in [2005]’
  254 | int in[MAXN]; //节点入度
      |     ^~
answer.code:35:5: note: ‘int in [2005]’ previously declared here
   35 | int in[MAXN]; //节点入度
      |     ^~
answer.code:255:5: error: redefinition of ...