Submission #479920

#	Time	Username	Problem	Language	Result	Execution time	Memory
479920		Ozy	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	1 ms	316 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;
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++;

        }
    }

    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);

        //posible falla de los 44 pts, ya que en vez de ser 10! es 10^10 la generacion
        tam = componente.size();
        if (tam == 1) continue;

        genera(1);
    }

    cout << res;
}

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