oj.uz

Submission #1112907

# Submission time Handle Problem Language Result Execution time Memory
1112907 2024-11-15T08:39:18 Z ntdaccode Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 64240 KB 
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e6+10;
const int N=1e3+10;
const int mod=1e9+7;
int n,m,q;
namespace sub1
{
  vector<ii> ke[M];
  vector<int> Q[M];
  bool dd[M];

  void dfs(int u,int pre,int p) {
    //cout << u <<" " <<  pre << " "   << p <<  "\n";
    dd[u] = true;
    for(ii tmp : ke[u]) {
        int v = tmp.first;
        int idx = tmp.second;
        if(v == p) continue;

        int nxt = 0,tt = 0;
        for(int i = 0; i < Q[idx].size(); i++) {
            tt = 1 - tt;
          if(tt && Q[idx][i] <= pre) {
            if(i != Q[idx].size()-1) nxt = Q[idx][i + 1] - 1;
            else nxt = m;
          }
        }
        //cerr << u <<  ' ' << v << " " << idx << "\n";
        if(nxt) dfs(v,min(pre,nxt),u);
    }
  }

  void solve()
  {
    for(int i = 1;i <= n - 1; i++) {
      int u , v;
      cin >> u >> v;
      ke[u].pb({v,i});
      ke[v].pb({u,i});
    }

    for(int i = 1;i <= m; i++) {
      int idx;
      cin >> idx;
      Q[idx].pb(i);
    }
    for(int i = 1;i <= q; i++) {
      int root;
      int res  = 0;
      cin >> root;
      dfs(root,1e9,0);
      for(int i = 1;i <= n; i++) res += dd[i];
      for(int i = 1;i <= n; i++) dd[i] = 0;
      cout << res << "\n";
    }

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

  cin >> n >> m >> q;
  sub1::solve();

}

Compilation message

synchronization.cpp: In function 'void sub1::dfs(long long int, long long int, long long int)':
synchronization.cpp:28:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = 0; i < Q[idx].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
synchronization.cpp:31:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if(i != Q[idx].size()-1) nxt = Q[idx][i + 1] - 1;
      |                ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
synchronization.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48208 KB Output is correct
2 Correct 12 ms 48208 KB Output is correct
3 Correct 16 ms 48220 KB Output is correct
4 Correct 11 ms 48208 KB Output is correct
5 Correct 14 ms 48208 KB Output is correct
6 Correct 15 ms 48208 KB Output is correct
7 Correct 20 ms 49232 KB Output is correct
8 Correct 24 ms 49232 KB Output is correct
9 Correct 21 ms 49232 KB Output is correct
10 Correct 75 ms 59136 KB Output is correct
11 Correct 74 ms 59220 KB Output is correct
12 Correct 57 ms 58696 KB Output is correct
13 Correct 59 ms 58296 KB Output is correct
14 Correct 61 ms 58184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 61888 KB Output is correct
2 Correct 50 ms 60360 KB Output is correct
3 Correct 50 ms 62740 KB Output is correct
4 Correct 45 ms 62572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47184 KB Output is correct
2 Correct 21 ms 47184 KB Output is correct
3 Correct 21 ms 47460 KB Output is correct
4 Correct 20 ms 47440 KB Output is correct
5 Correct 20 ms 47448 KB Output is correct
6 Correct 21 ms 47528 KB Output is correct
7 Correct 67 ms 49232 KB Output is correct
8 Correct 4245 ms 58676 KB Output is correct
9 Correct 4179 ms 59576 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4155 ms 59480 KB Output is correct
2 Execution timed out 8067 ms 64240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48208 KB Output is correct
2 Correct 18 ms 48076 KB Output is correct
3 Correct 15 ms 48208 KB Output is correct
4 Correct 18 ms 48208 KB Output is correct
5 Correct 24 ms 48208 KB Output is correct
6 Correct 119 ms 49252 KB Output is correct
7 Correct 6195 ms 60080 KB Output is correct
8 Correct 4138 ms 59464 KB Output is correct
9 Execution timed out 8048 ms 59200 KB Time limit exceeded
10 Halted 0 ms 0 KB -