QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141970#6526. Canvascy1999WA 5ms17452kbC++3.4kb2023-08-18 08:16:532023-08-18 08:16:56

Judging History

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

  • [2023-08-18 08:16:56]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:17452kb
  • [2023-08-18 08:16:53]
  • 提交

answer

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 500000, M = 500000;
int n, m;

struct Op
{
	int x, kx, y, ky;
	int id;
	bool operator < (const Op &t) const
	{
		int t1 = kx + ky, t2 = t.kx + t.ky;
		return t1 > t2;
	}
}op[M + 5];
int a[N + 5];

void init()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d %d %d %d", &op[i].x, &op[i].kx, &op[i].y, &op[i].ky);
		op[i].id = i;
	}
}

void deal(int x)
{
//	printf("%d 111\n", x);
	if(!a[op[x].x])
	{
		a[op[x].x] = op[x].kx;
	}
	if(!a[op[x].y])
	{
		a[op[x].y] = op[x].ky;
	}
}

struct Edge
{
	int v, w, nxt;
}edge[M + 5];
int head[N + 5], cnte;
void adde(int u, int v, int w)
{
//	printf("%d %d %d\n", u, v, w);
	edge[++cnte] = (Edge){v, w, head[u]};
	head[u] = cnte;
}

int dfn[N + 5], low[N + 5], cntn;
bool ins[N + 5];
stack <int> s;
int sid[N + 5], cnts;
vector <int> sv[N + 5];
void tarjan(int u)
{
//	printf("%d 222\n", u);
	dfn[u] = low[u] = ++cntn;
	s.push(u);
	ins[u] = 1;
	for(int i = head[u]; i; i = edge[i].nxt)
	{
		int v = edge[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(ins[v])
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(low[u] == dfn[u])
	{
		cnts++;
		while(1)
		{
			int x = s.top();
			s.pop();
			sid[x] = cnts;
//			printf("114514\n");
			sv[cnts].push_back(x);
//			printf("%d %d 666\n", cnts, x);
			ins[x] = 0;
			if(x == u)
			{
				break;
			}
		}
	}
}
int deg[N + 5];

vector <int> out;
bool vis[N + 5];
void dfs(int u)
{
//	printf("%d 222\n", u);
	vis[u] = 1;
	for(int i = head[u]; i; i = edge[i].nxt)
	{
		int w = edge[i].w;
		out.push_back(op[w].id);
		deal(w);
		int v = edge[i].v;
		if(!vis[v])
		{
			dfs(v);
		}
	}
}

void solve()
{
	sort(op + 1, op + m + 1);
//	for(int i = 1; i <= m; i++)
//	{
//		printf("%d %d\n", op[i].kx, op[i].ky);
//	}
	int p;
	for(p = 1; p <= m; p++)
	{
		if(op[p].kx + op[p].ky != 4)
		{
			break;
		}
		out.push_back(op[p].id);
		deal(p);
	}
	for(; p <= m; p++)
	{
		if(op[p].kx + op[p].ky != 3)
		{
			break;
		}
		if(op[p].kx == 1)
		{
			adde(op[p].x, op[p].y, p);
		}
		else
		{
			adde(op[p].y, op[p].x, p);
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
//	for(int i = 1; i <= n; i++)
//	{
//		printf("%d\n", sid[i]);
//	}
	for(int i = 1; i <= cnte; i++)
	{
		deg[sid[edge[i].v]]++;
	}
	for(int i = 1; i <= cnts; i++)
	{
		if(deg[i])
		{
			continue;
		}
		int len = sv[i].size();
		for(int j = 0; j < len; j++)
		{
			int u = sv[i][j];
//			printf("%d %d 333\n", u, j);
			if(a[u] == 2 || j == len - 1)
			{
				dfs(u);
			}
		}
	}
	for(; p <= m; p++)
	{
		deal(p);
		out.push_back(op[p].id);
	}
	int sum = 0;
	for(int i = 1; i <= n; i++)
	{
		sum += a[i];
	}
	printf("%d\n", sum);
	int len = out.size();
	for(int i = len - 1; i >= 0; i--)
	{
		printf("%d ", out[i]);
	}
	printf("\n");
}

void clr()
{
	for(int i = 1; i <= n; i++)
	{
		a[i] = 0;
	}
	for(int i = 1; i <= n; i++)
	{
		head[i] = 0;
	}
	cnte = 0;
	cntn = 0;
	for(int i = 1; i <= cnts; i++)
	{
		sv[i].clear();
		deg[i] = 0;
	}
	cnts = 0;
	out.clear();
	for(int i = 1; i <= n; i++)
	{
		vis[i] = 0;
		dfn[i] = 0;
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		init();
		solve();
		clr();		
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 17452kb

input:

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

output:

7
4 2 1 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 16888kb

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

5
13 12 

result:

wrong output format Unexpected end of file - int32 expected (test case 1)