QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141972 | #6526. Canvas | cy1999 | WA | 6ms | 18800kb | C++ | 3.1kb | 2023-08-18 08:24:58 | 2023-08-18 08:25:00 |
Judging History
answer
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#define int long long
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("%lld %lld", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%lld %lld %lld %lld", &op[i].x, &op[i].kx, &op[i].y, &op[i].ky);
op[i].id = i;
}
}
void deal(int 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)
{
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)
{
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;
sv[cnts].push_back(x);
ins[x] = 0;
if(x == u)
{
break;
}
}
}
}
int deg[N + 5];
vector <int> out;
bool vis[N + 5];
void dfs(int 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);
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 <= 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];
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("%lld\n", sum);
int len = out.size();
for(int i = len - 1; i >= 0; i--)
{
printf("%lld ", 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;
}
}
signed main()
{
int T;
scanf("%lld", &T);
while(T--)
{
init();
solve();
clr();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 16960kb
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: 6ms
memory: 18800kb
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)