#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
vector<int> newadj[nax];
bool vis[nax];
int tab[nax];
bool state[nax];
long long sz[nax];
int res[nax];
bool compare(int x,int y){
return tab[x]>tab[y];
}
struct node{
int child,par,x,p;
};
struct compare2{
bool operator()(node const& p1, node const& p2)
{
if(p1.child!=p2.child) return p1.child < p2.child;
else return p1.par > p2.par;
}
};
void build(int x){
vis[x]=true;
priority_queue<node,vector<node>,compare2> pq;
for(auto u:adj[x]){
pq.push({tab[u],tab[x],u,x});
}
while(!pq.empty()){
auto cur=pq.top();
pq.pop();
if(vis[cur.x]) continue;
//cout <<cur.x<<" "<<cur.p<<endl;
newadj[cur.x].pb(cur.p);
newadj[cur.p].pb(cur.x);
vis[cur.x]=true;
for(auto u:adj[cur.x]){
pq.push({tab[u],tab[cur.x],u,cur.x});
}
}
}
void dfs(int x,int p){
sz[x]=tab[x];
//cout <<newadj[x].size()<<" "<<x<<endl;
for(auto u:newadj[x]){
if(u==p) continue;
dfs(u,x);
sz[x]+=sz[u];
}
if(p!=-1){
if(sz[x]>=tab[p]) state[x]=1;
else state[x]=0;
}
}
void ans(int x,int p){
if(state[x]==0) return;
res[x]=1;
for(auto u:newadj[x]){
if(u==p) continue;
ans(u,x);
}
}
int main() {
int n,m;
cin>>n>>m;
pair<int,int> mx={-1,-1};
for (int i = 0; i < n; ++i)
{
cin>>tab[i];
if(mx.fi<tab[i]){
mx={tab[i],i};
}
}
for (int i = 0; i < m; ++i)
{
int x,y;
cin>>x>>y;
x--;y--;
if(tab[x]==tab[y]){
adj[x].pb(y);
adj[y].pb(x);
}else if(tab[x]>tab[y]){
adj[x].pb(y);
}else{
adj[y].pb(x);
}
}
for (int i = 0; i < n; ++i)
{
sort(adj[i].begin(),adj[i].end(),compare);
}
build(mx.se);
state[mx.se]=true;
dfs(mx.se,-1);
ans(mx.se,-1);
for (int i = 0; i < n; ++i)
{
cout <<res[i];
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
10072 KB |
Output is correct |
2 |
Correct |
4 ms |
9820 KB |
Output is correct |
3 |
Correct |
4 ms |
9864 KB |
Output is correct |
4 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9820 KB |
Output is correct |
2 |
Correct |
6 ms |
9840 KB |
Output is correct |
3 |
Correct |
190 ms |
34692 KB |
Output is correct |
4 |
Correct |
165 ms |
34640 KB |
Output is correct |
5 |
Correct |
206 ms |
27500 KB |
Output is correct |
6 |
Correct |
230 ms |
28388 KB |
Output is correct |
7 |
Correct |
202 ms |
28164 KB |
Output is correct |
8 |
Correct |
230 ms |
30544 KB |
Output is correct |
9 |
Correct |
174 ms |
26804 KB |
Output is correct |
10 |
Correct |
166 ms |
25152 KB |
Output is correct |
11 |
Correct |
201 ms |
31288 KB |
Output is correct |
12 |
Correct |
194 ms |
28324 KB |
Output is correct |
13 |
Correct |
223 ms |
43828 KB |
Output is correct |
14 |
Correct |
163 ms |
43996 KB |
Output is correct |
15 |
Correct |
203 ms |
46020 KB |
Output is correct |
16 |
Correct |
161 ms |
45000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9816 KB |
Output is correct |
2 |
Incorrect |
494 ms |
19152 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9820 KB |
Output is correct |
2 |
Incorrect |
156 ms |
19284 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
10072 KB |
Output is correct |
2 |
Correct |
4 ms |
9820 KB |
Output is correct |
3 |
Correct |
4 ms |
9864 KB |
Output is correct |
4 |
Incorrect |
5 ms |
9820 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |