Submission #1199191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199191		Ronin13	JOI tour (JOI24_joitour)	C++20	6 / 100	2417 ms	273144 KiB

joitour

#include "joitour.h"
#include <bits/stdc++.h>
using ll = long long ;
using ull = unsigned ll;
#define f first 
#define s second 
#define pb push_back
#define epb emplace_back
using namespace std;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

struct Data{

  vector <ll> f[3];
  int n;
  vector <ll> cnt;
  vector <vector<ll>>cnts;

  Data() {
    cnt.resize(5);
  }
  void add(int pos, int val, int id) {
    while(pos < f[id].size()) {
      f[id][pos] += val;
      pos += (pos & -pos);
    }
  }
  ll get(int pos, int id) {
    ll res = 0;
    while(pos) {
      res += f[id][pos];
      pos -= (pos & -pos);
    }
    return res;
  }
  ll get(int l, int r, int id) {
    return get(r, id) - get(l - 1, id);
  }
};


const int nmax = 200001;
vector <vector <int>>vec(nmax);
vector <vector <int>>sz(nmax);
vector <vector<int>>in(nmax);
vector <vector <int>>g(nmax);
vector <int>y(nmax);
vector <vector<int>>lead_in(nmax);
Data dt[nmax];
vector <bool> blocked(nmax);
vector <int> siz(nmax);
ll ans;
int timer = 1;

vector <vector<ll>>cnt(nmax, vector<ll>(5));

void dfs(int v, int e) {
//  cout << v << ' ';
  siz[v] = 1;
  for(int to : g[v]) {
    if(to == e || blocked[to]) continue;
    dfs(to, v);
    siz[v] += siz[to];
  }
}

int find_cent(int v, int e, int n) {
  for(int to : g[v]) {
    if(blocked[to] || to == e) continue;
    if(siz[to] * 2 >= n) return find_cent(to, v, n);
  }
  return v;
}

void clear_dfs(int v, int e) {
  siz[v] = 0;
  for(int to : g[v]) {
    if(to == e || blocked[to]) continue;
    clear_dfs(to, v);
  }
  siz[v] = 0;
}


void update_cnt(int v, int to, bool x = false) {
  for(int i = 0; i < 5; i++) cnt[v][i] += cnt[to][i];
  if(y[v] == 1 && !x) {
    cnt[v][3] += cnt[to][0];
    cnt[v][4] += cnt[to][2];
  }
}

void DFS(int v, int e, int num, vector<int>&visited) {
    in[v].pb(timer++);
    lead_in[v].pb(num);
    sz[v].pb(1);
    visited.pb(v);
    for(int j = 0; j < 5; j++) cnt[v][j] = 0;
    for(int to : g[v]) {
      if(to == e || blocked[to]) continue;
      DFS(to, v, num, visited);
      update_cnt(v, to);
    }
    cnt[v][y[v]]++;
}

void clearDFS(int v, int e) {
  cnt[v].assign(5, 0);
  for(int to : g[v]) {
    if(to == e || blocked[to]) continue;
    clearDFS(to, v);
  }
}

void decompose(int v) {
  dfs(v, v);
  int n = siz[v];
  int x = find_cent(v, v, siz[v]);

  clear_dfs(v, v);
  timer = 1;
  sz[x].pb(n);
  int num = 0;
  vector <int> visited;
  for(int to : g[x]) {
    if(blocked[to]) continue;
    DFS(to, x, num, visited);
    update_cnt(x, to, true);
    dt[x].cnts.pb(cnt[to]);
    num++;
  }

  cnt[x][y[x]]++;
  for(int j = 0; j< 3; j++) {
    dt[x].f[j].resize(n + 1);
  }
  dt[x].cnt = cnt[x];
  for(auto to : visited) {
    if(y[to] != 1) {
      dt[x].add(in[to].back(), 1, y[to]);
    }
  }
  clearDFS(x, x);
  timer = 1;
  blocked[x] = true;
  for(int to : g[x]) {
      if(!blocked[to]) decompose(to);
  }
}


void init(int n, std::vector<int> f, std::vector<int> u, std::vector<int> v,int q) {
    for(int i = 0; i < f.size(); i++) {
      y[i] = f[i];
    }
   // cout << 1;
    for(int i = 0; i < u.size(); i++) {
      g[u[i]].pb(v[i]);
      g[v[i]].pb(u[i]);
    }
   // cout << 1;
    decompose(0);
   // cout << 1;
    for(int i = 0; i < n; i++) {
     
      for(auto to : dt[i].cnts) {
        ans += (dt[i].cnt[0] - to[0]) * to[4] + (dt[i].cnt[2] - to[2]) * to[3] + to[0] * (dt[i].cnt[4] - to[4]) + to[2] * (dt[i].cnt[3] - to[3]);
        if(y[i] == 1) {
          ans += to[2] * (dt[i].cnt[0] - to[0]) + to[0] * (dt[i].cnt[2] - to[2]);
        }
        if(y[i] == 0) {
          ans += to[4];
        }
        if(y[i] == 2) {
          ans += to[3];
        } 
      }
     // cout << ans << ' ';
      
    }
}

void change(int X, int Y) {}

long long num_tours() {
  
  return ans / 2;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14