Submission #116054

#	Time	Username	Problem	Language	Result	Execution time	Memory
116054		Arturgo	Synchronization (JOI13_synchronization)	C++14	100 / 100	4234 ms	113644 KiB

synchronization

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int nbServers, nbEvents, nbReqs;

vector<int> voisins[100 * 1000];
vector<pair<int, int>> links;

int nbInfos[100 * 1000];
int derInfos[100 * 1000];
bool isConnected[100 * 1000];

int curId = 0;
int ids[100 * 1000], rIds[100 * 1000];

int curPos = 0;
int positions[100 * 1000];

void dfs(int noeud, int parent = -1) {
  rIds[curId] = noeud;
  ids[noeud] = curId++;

  for(int voisin : voisins[noeud]) {
    if(voisin != parent)
      dfs(voisin, noeud);
  }

  positions[noeud] = curPos++;
}

set<int> arbre[(1 << 18)];

void updateServer(int server, int op) {
  int pos = positions[server] + (1 << 17);

  while(pos != 0) {
    if(op == -1) {
      arbre[pos].erase(-ids[server]);
    }
    else {
      arbre[pos].insert(-ids[server]);
    }
    pos /= 2;
  }
}

int getParent(int server) {
  int deb = positions[server] + (1 << 17);
  int fin = nbServers + (1 << 17);
  int bound = -ids[server];

  int mini = 0;
  while(deb < fin) {
    if(deb % 2 == 1) {
      auto it = arbre[deb].lower_bound(bound);
      if(it != arbre[deb].end()) {
	mini = min(mini, *it);
      }
      
      deb++;
    }
    if(fin % 2 == 1) {
      fin--;

      auto it = arbre[fin].lower_bound(bound);
      if(it != arbre[fin].end()) {
	mini = min(mini, *it);
      }
    }
    deb /= 2;
    fin /= 2;
  }
  
  return rIds[-mini];
}

void update(int link) {
  int haut = links[link].first;
  int bas = links[link].second;
  if(ids[haut] >= ids[bas]) swap(haut, bas);
  
  if(isConnected[link]) {
    derInfos[link] = nbInfos[bas] = nbInfos[getParent(haut)];
    updateServer(bas, 1);
  }
  else {
    nbInfos[getParent(haut)] += nbInfos[bas] - derInfos[link];
    updateServer(bas, -1);
  }

  isConnected[link] = !isConnected[link];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbServers >> nbEvents >> nbReqs;

  for(int iServer = 0;iServer < nbServers - 1;iServer++) {
    int deb, fin;
    cin >> deb >> fin;
    voisins[deb - 1].push_back(fin - 1);
    voisins[fin - 1].push_back(deb - 1);
    links.push_back({deb - 1, fin - 1});
  }

  dfs(0);

  for(int iServer = 0;iServer < nbServers;iServer++) {
    nbInfos[iServer] = 1;
    updateServer(iServer, 1);
  }

  for(int iEvent = 0;iEvent < nbEvents;iEvent++) {
    int link;
    cin >> link;
    update(link - 1);
  }

  for(int iReq = 0;iReq < nbReqs;iReq++) {
    int server;
    cin >> server;
    cout << nbInfos[getParent(server - 1)] << endl;
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40