oj.uz

Submission #927148

# Submission time Handle Problem Language Result Execution time Memory
927148 2024-02-14T10:24:13 Z vjudge1 Paths (BOI18_paths) C++17
23 / 100
 3000 ms 6492 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("popcnt")
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define emb emplace_back
#define emc emplace
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
template <class type_key, class type_val>
using um = unordered_map<type_key, type_val>;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5+1;
int n, m, k;
int c[N];
vector<vector<int>> g(N);

int col;
int was[6];
void dfs( int v ) {
      was[c[v]] = 1;

      for( int to: g[v] ) {
            if( !was[c[to]] ) {
                  col++;
                  dfs(to);
            }
      }

      was[c[v]] = 0;
}

signed main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

      cin >> n >> m >> k;

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

      for( int i = 1; i <= m; i++ ) {
            int u, v;
            cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
      }

      ll ans = 0;
      for( int i = 1; i <= n; i++ ) {
            dfs(i);
            ans += col;
            col = 0;
      }

      cout << ans;

return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1996 ms 6492 KB Output is correct
2 Execution timed out 3027 ms 6148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1996 ms 6492 KB Output is correct
12 Execution timed out 3027 ms 6148 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Execution timed out 3045 ms 3928 KB Time limit exceeded
3 Halted 0 ms 0 KB -