- 技术
- Codeforces Round #652 (Div. 2) E - DeadLee (贪心)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std
;
#define inf 0x7fffffff
#define ll long long
#define mod (1000000007)
#define maxn 200005
int num
[maxn
],have
[maxn
];
pair
<int,int> node
[maxn
];
vector
<int> v
[maxn
], ans
;
queue
<int> q
;
bool vis
[maxn
];
int main(){
int i
, n
, j
, k
, t
, m
, x
, y
;
scanf("%d%d",&n
,&m
);
for(i
=1;i
<=n
;i
++) scanf("%d",&have
[i
]);
for(i
=1;i
<=m
;i
++){
scanf("%d%d",&x
,&y
);
num
[x
]++;num
[y
]++;
node
[i
]={x
,y
};
v
[x
].push_back(i
);
v
[y
].push_back(i
);
}
for(i
=1;i
<=n
;i
++) if(num
[i
]<=have
[i
]) q
.push(i
);
while(!q
.empty()){
int cur
=q
.front();q
.pop();
int lim
=v
[cur
].size();
for(i
=0;i
<lim
;i
++){
k
= v
[cur
][i
];
if(vis
[k
]) continue;
vis
[k
]=1;
ans
.push_back(k
);
int to
=node
[k
].first
;
if(to
==cur
) to
=node
[k
].second
;
if(--num
[to
]==have
[to
]) q
.push(to
);
}
}
if(ans
.size()!=m
) printf("DEAD\n");
else{
printf("ALIVE\n");
for(i
=m
-1;i
>=0;i
--) printf("%d ",ans
[i
]);
printf("\n");
}
}
Processed:
0.049, SQL:
9
