Submission #1097848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097848		VinhLuu	Stranded Far From Home (BOI22_island)	C++17	100 / 100	259 ms	116220 KiB

island

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define all(vin) vin.begin(), vin.end()

using namespace std;

typedef pair<int,int> pii;
typedef pair<pii,int> tp;
const int N = 1e6 + 2;
//const int oo = 1e16;

int n, m, a[N], b[N];
vector<int> p[N], g[N], vr[N];

int w[N], pa[N], sz[N], t[N], mx[N];

int fin(int u){
  return pa[u] == u ? u : pa[u] = fin(pa[u]);
}

void dsu(int x,int y,int j){
  if(fin(x) == fin(y)) return;


  x = fin(x);
  y = fin(y);
  int px = mx[x], py = mx[y];
  g[px].push_back(py);
  t[py] = min(t[py], j);
  if(a[px] == a[py]) mx[y] = mx[x];
//  cerr << px << " " << py << " " << j << " p\n";
  if(sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  pa[y] = x;
  w[x] += w[y];

  if(a[mx[y]] > a[mx[x]]) mx[x] = mx[y];
//  else if(a[mx[y]] == a[mx[x]] && )
}

void dfs(int u,int v){
  for(auto j : g[u]) if(j != v){
    t[j] = min(t[j], t[u]);
    dfs(j, u);
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> m;

  vector<int> rrh;
  for(int i = 1; i <= n; i ++){
    cin >> a[i];
    rrh.push_back(a[i]);
  }
  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());
  for(int i = 1; i <= n; i ++){
    b[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
    vr[b[i]].push_back(i);
  }
  for(int i = 1; i <= m; i ++){
    int x, y; cin >> x >> y;
    p[x].push_back(y);
    p[y].push_back(x);
  }
//  for(int i = 1; i <= n; i ++) cerr << i << " " << a[i] << " y\n";

  for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1, w[i] = a[i], t[i] = 1, mx[i] = i;

  for(int k = 1; k <= (int)rrh.size(); k ++){
    int val = rrh[k - 1];
    for(auto i : vr[k]){
      for(auto j : p[i]) if(a[j] == a[i]){
        dsu(i, j, 1);
      }else if(a[j] < a[i]){
        if(w[fin(j)] >= a[i]) dsu(i, j, 1);
        else dsu(i, j, 0);
      }
    }
  }
  int root = mx[fin(1)];
  dfs(root, 0);
  for(int i = 1; i <= n; i ++) cout << t[i];
}
/*
12 16
92 43 33 70 2 19 58 78 79 34 22 19
1 2
1 3
3 4
1 5
5 6
1 7
3 8
3 9
3 10
1 11
2 12
12 2
4 10
3 9
4 3
5 12
*/

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:81:9: warning: unused variable 'val' [-Wunused-variable]
   81 |     int val = rrh[k - 1];
      |         ^~~
island.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
island.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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