Submission #533569

#	Time	Username	Problem	Language	Result	Execution time	Memory
533569		N1NT3NDO	Šarenlist (COCI22_sarenlist)	C++17	10 / 110	87 ms	316 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll mod = 1e9 + 7;
const int N = 70;
vector<int> g[N];
int n, m, len[N][N], who, l[N], r[N], col[N], F;
bool bad[N];
ll k, ans;
vector< pair< int, int> > vec;
bool ok = 0;

void dfs(int v, int pr, vector<int> vc)
{
    if (v == F)
    {
        set<int> se;
        for(auto u : vc) se.insert(u);
        if (sz(se) >= 2)
          ok = 1;

        return;
    }

    for(int i = 0; i < sz(vec); i++)
    {
        int a = vec[i].fi, b = vec[i].sd;
        if (v != a && v != b) continue;
        if (v == a && b != pr)
        {
            vc.pb(col[i]);
            dfs(b, v, vc);
            vc.pop_back();
        }
        else if (b == v && a != pr)
        {
            vc.pb(col[i]);
            dfs(a, v, vc);
            vc.pop_back();
        }
    }
}

ll f(ll x)
{
    ll res = 1;
    for(ll i = 2; i <= x; i++) res = (res * i) % mod;
    return res;
}

void group4()
{
    int ans = 0;
    for(int mask = 0; mask < (1 << sz(vec)); mask++)
    {
        for(int i = 0; i < sz(vec); i++)
          if (mask & (1 << i))
            col[i] = 1;
          else col[i] = 2;

        bool bad = 0;

        for(int i = 1; i <= m; i++)
          {
              ok = 0;
              F = r[i];
              dfs(l[i], l[i], {});
              if (!ok)
              {
                  bad = 1;
                  break;
              }
          }

        if (!bad) ans++;
    }

    cout << ans;
}

void dfs2(int v, int pr, int d)
{
    len[who][v] = d;
    for(auto u : g[v])
    {
        if (u == pr) continue;
        dfs2(u, v, d + 1);
    }
}

void dfs3(int v, int pr, vector< int > vc)
{
    if (v == F)
    {
        for(auto u : vc) bad[u] = 1;
        return;
    }

    for(int i = 0; i < sz(vec); i++)
    {
        int a = vec[i].fi, b = vec[i].sd;
        if (v != a && v != b) continue;
        if (v == a && b != pr)
        {
            vc.pb(i);
            dfs3(b, v, vc);
            vc.pop_back();
        }
        else if (b == v && a != pr)
        {
            vc.pb(i);
            dfs3(a, v, vc);
            vc.pop_back();
        }
    }
}

void group1()
{

    for(int i = 1; i <= n; i++)
    {
        who = i;
        dfs2(i, i, 0);
    }

    ans = 1;
    for(int i = 1; i <= m; i++)
    {
        int a = l[i], b = r[i];
        ll d = len[a][b];


        if (k < d)
        {
            cout << 0;
            exit(0);
        }

        ll cur = k;
        while(d) ans = (ans * cur) % mod, d--, cur--;

        F = r[i];
        dfs3(l[i], l[i], {});
    }

    for(int i = 0; i < sz(vec); i++)
      if (!bad[i])
        ans = (ans * k) % mod;

    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

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

    for(int i = 1; i <= m; ++i) cin >> l[i] >> r[i];

    if (n <= 15 && k == 2)
        group4();
    else group1();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 65