제출 #599731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599731		Mounir	Stranded Far From Home (BOI22_island)	C++14	10 / 100	263 ms	46100 KiB

island

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
#define int long long
using namespace std;

const int N = 3e5;
int sousArbre[N];
vector<int> enfants[N];
vector<int> winner[N];
int vals[N];

void dfs(int noeud){
      sousArbre[noeud] = vals[noeud];
      for (int enfant : enfants[noeud]){
            dfs(enfant);
            sousArbre[noeud] += sousArbre[enfant];
            if (sousArbre[enfant] >= vals[noeud])
                  winner[noeud].pb(enfant);
      }
}

bool vainqueur[N];
void complete(int noeud){
      vainqueur[noeud] = true;
      for (int enf : winner[noeud])
            complete(enf);
}

signed main(){ 
      int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
      for (int i = 0; i < nNoeuds; ++i)
            cin >> vals[i];
      for (int i = 0; i < nAretes; ++i){
            int u, v; cin >> u >> v;
            u--; v--;
            if (u > v)
                  swap(u, v);
            enfants[u].pb(v);
      }
      dfs(0);
      complete(0);
      for(int i = 0; i < nNoeuds; ++i)
            cout << vainqueur[i];
      cout << endl;
      return 0;   
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35