oj.uz

Submission #738698

# Submission time Handle Problem Language Result Execution time Memory
738698 2023-05-09T12:15:52 Z Sam_a17 Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 20744 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

int ka() {
	int x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
vector<int> adj[N];
vector<int> dep[N];
int n, m, a[N];

void dfs(int node, int parent, int depth) {
  if(depth) {
    dep[depth].push_back(a[node]);
  }

  for(auto i: adj[node]) {
    if(i == parent) continue;
    dfs(i, node, depth + 1);
  }
}

void solve_() {
  cin >> n >> m;
  for(int i = 1; i <= n - 1; i++) {
    int x, y; cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  for(int i = 1; i <= n; i++) {
    dfs(i, 0, 0);

    set<int> st;

    for(int j = 1; j <= n; j++) {
      if(sz(dep[j]) == 1) {
        st.insert(dep[j][0]);
      }
      dep[j].clear();
    }

    cout << sz(st) << '\n';
  }

}
 
int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

joi2019_ho_t5.cpp: In function 'void setIO(std::string)':
joi2019_ho_t5.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 64 ms 9852 KB Output is correct
3 Correct 58 ms 9856 KB Output is correct
4 Correct 85 ms 10108 KB Output is correct
5 Correct 75 ms 9860 KB Output is correct
6 Correct 117 ms 9948 KB Output is correct
7 Correct 81 ms 9948 KB Output is correct
8 Correct 71 ms 9844 KB Output is correct
9 Correct 77 ms 9860 KB Output is correct
10 Correct 73 ms 9980 KB Output is correct
11 Correct 77 ms 10000 KB Output is correct
12 Correct 42 ms 9812 KB Output is correct
13 Correct 114 ms 9936 KB Output is correct
14 Correct 78 ms 10656 KB Output is correct
15 Correct 82 ms 10572 KB Output is correct
16 Correct 42 ms 9832 KB Output is correct
17 Correct 84 ms 12476 KB Output is correct
18 Correct 79 ms 10832 KB Output is correct
19 Correct 74 ms 9840 KB Output is correct
20 Correct 250 ms 10008 KB Output is correct
21 Correct 95 ms 10052 KB Output is correct
22 Correct 68 ms 9856 KB Output is correct
23 Correct 91 ms 9872 KB Output is correct
24 Correct 76 ms 9932 KB Output is correct
25 Correct 73 ms 9932 KB Output is correct
26 Correct 48 ms 9864 KB Output is correct
27 Correct 188 ms 9976 KB Output is correct
28 Correct 159 ms 12420 KB Output is correct
29 Correct 91 ms 10876 KB Output is correct
30 Correct 36 ms 9932 KB Output is correct
31 Correct 126 ms 12608 KB Output is correct
32 Correct 95 ms 10896 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 17472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 20744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 64 ms 9852 KB Output is correct
3 Correct 58 ms 9856 KB Output is correct
4 Correct 85 ms 10108 KB Output is correct
5 Correct 75 ms 9860 KB Output is correct
6 Correct 117 ms 9948 KB Output is correct
7 Correct 81 ms 9948 KB Output is correct
8 Correct 71 ms 9844 KB Output is correct
9 Correct 77 ms 9860 KB Output is correct
10 Correct 73 ms 9980 KB Output is correct
11 Correct 77 ms 10000 KB Output is correct
12 Correct 42 ms 9812 KB Output is correct
13 Correct 114 ms 9936 KB Output is correct
14 Correct 78 ms 10656 KB Output is correct
15 Correct 82 ms 10572 KB Output is correct
16 Correct 42 ms 9832 KB Output is correct
17 Correct 84 ms 12476 KB Output is correct
18 Correct 79 ms 10832 KB Output is correct
19 Correct 74 ms 9840 KB Output is correct
20 Correct 250 ms 10008 KB Output is correct
21 Correct 95 ms 10052 KB Output is correct
22 Correct 68 ms 9856 KB Output is correct
23 Correct 91 ms 9872 KB Output is correct
24 Correct 76 ms 9932 KB Output is correct
25 Correct 73 ms 9932 KB Output is correct
26 Correct 48 ms 9864 KB Output is correct
27 Correct 188 ms 9976 KB Output is correct
28 Correct 159 ms 12420 KB Output is correct
29 Correct 91 ms 10876 KB Output is correct
30 Correct 36 ms 9932 KB Output is correct
31 Correct 126 ms 12608 KB Output is correct
32 Correct 95 ms 10896 KB Output is correct
33 Execution timed out 2047 ms 17472 KB Time limit exceeded
34 Halted 0 ms 0 KB -