제출 #927148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927148		vjudge1	Paths (BOI18_paths)	C++17	23 / 100	3045 ms	6492 KiB

paths

#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 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30