oj.uz

Submission #533569

# Submission time Handle Problem Language Result Execution time Memory
533569 2022-03-06T10:11:41 Z N1NT3NDO Šarenlist (COCI22_sarenlist) C++17
10 / 110
 87 ms 316 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 3 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 14 ms 316 KB Output is correct
5 Correct 30 ms 296 KB Output is correct
6 Correct 87 ms 296 KB Output is correct
7 Correct 65 ms 292 KB Output is correct

Subtask #5
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -