제출 #1275416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275416		Tai_xiu	Šarenlist (COCI22_sarenlist)	C++20	25 / 110	1 ms	580 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define Z int
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) ((Z)(a).size())
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
Z dx4[]= {-1,1,0,0};
Z dy4[]= {0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const string NAME = "coloring";
vi g[77], g1[77];
Z par[77];
vi path[20];
Z n , m, k ;
Z idx[77][77];
bool check[77];
Z mu(Z num ,Z x )
{
    Z ans = 1;
    FOR(i, 1, x) ans = ans * num % mod;
    return ans;
}
Z h[77];
void get(Z u, Z v , vi & tam)
{

    if (h[u] > h[v]) swap(u,v);
    vi lt;
    while( h[v] > h[u]) {
        tam.pb(v);
        v = par[v];
    }
    while ( u  == v) {
         vi cc;
         cc.pb(u);
        FOR(i, 0, len(tam)- 2 ) cc.pb(idx[tam[i]][tam[i + 1]]);
        tam = cc;
        return ;
    }
    while(u != v){
        lt.pb(u);
        tam.pb(v);
        u = par[u];
        v = par [v];
    }
    tam.pb(u);
    REP(i, len(lt) - 1, 0) tam.pb(lt[i]);
    vi cc;
    FOR(i, 0, len(tam)- 2 ) cc.pb(idx[tam[i]][tam[i + 1]]);
    tam = cc;
}
void dfs(Z u, Z p  = - 1)
{
    for (Z v : g[u]){
        if (v == p) continue;
        h[v] = h[u] + 1;
        par[v] = u;
        dfs(v, u);

    }
}
void dfs1(Z u, Z p = - 1)
{
    check[u] = 1;
    for (Z v : g1[u]){
        if (check[v]) continue;
        dfs1(v, u);
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   // freopen((NAME + ".inp").c_str(),"r", stdin);
  //  freopen((NAME + ".out").c_str(),"w", stdout);

    cin >> n >> m >> k;
    FOR(i, 1, n - 1 ){
        Z u, v;
        cin >> u >> v;
        idx[u][v] = idx[v][u] = i;
        g[u].pb(v);
        g[v].pb(u);
    }
    h[1] = 1;
    dfs(1);
    FOR(i, 0, m - 1){
        Z u, v;
        cin >> u >> v;
        get(u,v, path[i]);
    }

    Z sol  = mu(k, n - 1);
//    FOR(i, 0, m- 1){
//        for (Z v : path[i]) cout << v <<" ";
//        cout << '\n';
//    }
//
//    cout << sol << '\n';
    FOR(mask, 1, (1 << m) - 1){
        memset(check,0,sizeof(check));
        FOR(i, 1, n) g1[i].clear();
        FOR(i, 0, m - 1){
            if (mask >> i & 1){
                FOR(j, 0 , len(path[i]) - 2){
                    g1[path[i][j]].pb(path[i][j + 1]);
                    g1[path[i][j + 1]].pb(path[i][j]);
                }
            }
        }
        Z cnt = 0;
        FOR(i, 1, n - 1){
            if (!check[i]){
                ++ cnt;
                dfs1(i);
            }
        }
//        cout << mask << " " << cnt << '\n';
        if (__builtin_popcount(mask) % 2 == 0){
            sol = (sol + mu(k, cnt)) % mod;
        }
        else sol = (sol - mu(k, cnt) + mod) % mod;
    }
    cout << sol << '\n';
}

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