oj.uz

Submission #116054

# Submission time Handle Problem Language Result Execution time Memory
116054 2019-06-10T09:48:35 Z Arturgo Synchronization (JOI13_synchronization) C++14
100 / 100
 4234 ms 113644 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14976 KB Output is correct
2 Correct 15 ms 15104 KB Output is correct
3 Correct 15 ms 15104 KB Output is correct
4 Correct 15 ms 15104 KB Output is correct
5 Correct 15 ms 15104 KB Output is correct
6 Correct 22 ms 16000 KB Output is correct
7 Correct 165 ms 24264 KB Output is correct
8 Correct 186 ms 24312 KB Output is correct
9 Correct 159 ms 24440 KB Output is correct
10 Correct 3934 ms 108096 KB Output is correct
11 Correct 4129 ms 108032 KB Output is correct
12 Correct 2822 ms 112752 KB Output is correct
13 Correct 2332 ms 108132 KB Output is correct
14 Correct 2194 ms 107092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 109928 KB Output is correct
2 Correct 541 ms 108864 KB Output is correct
3 Correct 515 ms 111776 KB Output is correct
4 Correct 524 ms 111724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15232 KB Output is correct
2 Correct 15 ms 14976 KB Output is correct
3 Correct 14 ms 15104 KB Output is correct
4 Correct 15 ms 15104 KB Output is correct
5 Correct 16 ms 15104 KB Output is correct
6 Correct 24 ms 16000 KB Output is correct
7 Correct 202 ms 24820 KB Output is correct
8 Correct 3066 ms 113644 KB Output is correct
9 Correct 3115 ms 113532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3103 ms 113516 KB Output is correct
2 Correct 676 ms 112252 KB Output is correct
3 Correct 677 ms 112928 KB Output is correct
4 Correct 700 ms 113004 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15104 KB Output is correct
2 Correct 15 ms 15104 KB Output is correct
3 Correct 15 ms 15076 KB Output is correct
4 Correct 15 ms 15104 KB Output is correct
5 Correct 24 ms 15992 KB Output is correct
6 Correct 216 ms 24436 KB Output is correct
7 Correct 4234 ms 109016 KB Output is correct
8 Correct 2938 ms 113404 KB Output is correct
9 Correct 2380 ms 109184 KB Output is correct
10 Correct 2408 ms 108408 KB Output is correct
11 Correct 717 ms 111208 KB Output is correct
12 Correct 718 ms 111076 KB Output is correct
13 Correct 670 ms 112872 KB Output is correct