oj.uz

Submission #479921

# Submission time Handle Problem Language Result Execution time Memory
479921 2021-10-13T23:12:15 Z Ozy Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 1 ms 204 KB 
#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.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 37.0

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