Submission #479922

#	Time	Username	Problem	Language	Result	Execution time	Memory
479922		Ozy	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	0 ms	204 KiB

amusementpark

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 18
#define mod 998244353

lli n,m,a,b,tam,res,total,cant,op;
lli procesados[MAX+2],arr[MAX+2];
vector<lli> componente;
vector<lli> hijos[MAX+2],dir[MAX+2];

void creaComponente(lli pos) {
    procesados[pos] = 1;
    componente.push_back(pos);
    for(auto h : hijos[pos]) if (procesados[h] == 0) creaComponente(h);
}

void checa() {

    lli rparcial = 0;

    for (auto act : componente) {
        for (auto h : dir[act]) {

            if (arr[h] < arr[act]) rparcial++;

        }
    }

    cant++;
    res += rparcial;
    if (res >= mod) res -= mod;
}

void genera(lli k) {
    for (auto act : componente) {
        if (arr[act] > 0) continue;

        arr[act] = k;
        if (k == tam) checa();
        else genera(k+1);
        arr[act] = 0;
    }
}

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

    cin >> n >> m;
    rep(i,1,m) {
        cin >> a >> b;

        hijos[a].push_back(b);
        hijos[b].push_back(a);

        dir[a].push_back(b);
    }

    rep(i,1,n){
        if (procesados[i] == 1) continue;

        componente.clear();
        creaComponente(i);
        tam = componente.size();

        //posible falla de los 44 pts, ya que en vez de ser 10! es 10^10 la generacion

        if (tam == 1) continue;
        res = 0;
        cant = 0;
        genera(1);

        if (res == 0) continue;
        else if (total == 0) {total = res; op = cant;}
        else {
            total *= cant;
            total %= mod;

            res *= op;
            res %= mod;

            total += res;
            total %= mod;

            op *= cant;
            op %= mod;
        }
    }

    cout << total;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37