Submission #59835

#	Time	Username	Problem	Language	Result	Execution time	Memory
59835		gusfring	Synchronization (JOI13_synchronization)	C++14	30 / 100	173 ms	31856 KiB

synchronization

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll; 
typedef unsigned long long llu; 

const int INF = 987654321; 
const ll LINF = 1e15;  

const int MAXN = 200005;
const int MAXM = 200005;

int TIME, chk[MAXN];

int N, M, Q;
vector<int> Gph[MAXN];
int C[MAXN], D[MAXN], X[MAXN], Y[MAXN];

int parent[MAXN];

void DFS1 (int u){
  int i;
  chk[u] = TIME;
  for(i = 0; i < Gph[u].size(); i++){
    int v = Gph[u][i];
    if(chk[v] != TIME) {
        parent[v] = u;
        DFS1(v);
    }
  }
}

bool change[MAXN];

void DFS2 (int u) {
  chk[u] = TIME;
  for(int i = 0; i < Gph[u].size(); i++) {
      int v = Gph[u][i];
      if(chk[v] != TIME && change[v]) DFS2(v);
  }
}

int main() {
  int i, j, k;

	scanf("%d%d%d", &N, &M, &Q);
  for(i = 1; i < N; i++) {
      int u, v; scanf("%d%d", &u, &v);
      Gph[u].push_back(v);
      Gph[v].push_back(u);
      X[i] = u; Y[i] = v;
  }
  
  for(i = 1; i <= M; i++) scanf("%d", D+i);
  for(i = 1; i <= Q; i++) scanf("%d", C+i);
  
  if(Q == 1) {
      int r = C[1];
      ++TIME; DFS1(r);
      
      for(i = 1; i <= M; i++) {
          int &d = D[i];
          if(X[d] == parent[Y[d]]) d = Y[d];
          else d = X[d];
      }
      
      ++TIME;
      for(i = 1; i <= M; i++) change[D[i]] ^= true;
      DFS2(r);
      
      for(i = M; i > 0; i--) {
          int &d = D[i];
          change[d] ^= true;
          if(change[d] && chk[parent[d]] == TIME && chk[d] != TIME) DFS2(d);
      }
      
      int ret = 0;
      for(i = 1; i <= N; i++) {
          if(chk[i] == TIME) ++ret;
      }
      
      printf("%d\n", ret);
  }
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void DFS1(int)':
synchronization.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < Gph[u].size(); i++){
              ~~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void DFS2(int)':
synchronization.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < Gph[u].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:45:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j, k;
          ^
synchronization.cpp:45:13: warning: unused variable 'k' [-Wunused-variable]
   int i, j, k;
             ^
synchronization.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:49:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int u, v; scanf("%d%d", &u, &v);
                 ~~~~~^~~~~~~~~~~~~~~~
synchronization.cpp:55:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(i = 1; i <= M; i++) scanf("%d", D+i);
                           ~~~~~^~~~~~~~~~~
synchronization.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(i = 1; i <= Q; i++) scanf("%d", C+i);
                           ~~~~~^~~~~~~~~~~

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