QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31116 | #1984. Mentors | karamah123 | AC ✓ | 131ms | 35224kb | C++ | 10.9kb | 2022-05-03 04:50:34 | 2022-05-03 04:50:36 |
Judging History
answer
// This file contains implementations of some well-known graph algorithms.
// Written by Nofar Carmeli. Some code is based on the book Competitive Programming 3 by Steven and Felix Halim.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
const int INF = 1e9;
/********** Topological Sort **********/
// input: directed graph (g[u] contains the neighbors of u, nodes are named 0,1,...,|V|-1).
// output: is g a DAG (return value), a topological ordering of g (order).
// comment: order is valid only if g is a DAG.
// time: O(V+E).
bool topological_sort(const vvi& g, vi& order) {
// compute indegree of all nodes
vi indegree (g.size(), 0);
for (int v=0; v<g.size(); v++) for (int u : g[v]) indegree[u]++;
// order sources first
order = vector<int>();
for (int v=0; v<g.size(); v++) if (indegree[v] == 0) order.push_back(v);
// go over the ordered nodes and remove outgoing edges,
// add new sources to the ordering
for (int i=0; i<order.size(); i++) for (int u : g[order[i]]) {
indegree[u]--;
if (indegree[u]==0) order.push_back(u);
}
return order.size()==g.size();
}
/********** Strongly Connected Components **********/
const int UNSEEN = -1;
const int SEEN = 1;
void KosarajuDFS(const vvi& g, int u, vi& S, vi& colorMap, int color) {
// DFS on digraph g from node u:
// visit a node only if it is mapped to the color UNSEEN,
// Mark all visited nodes in the color map using the given color.
// input: digraph (g), node (v), mapping:node->color (colorMap), color (color).
// output: DFS post-order (S), node coloring (colorMap).
colorMap[u] = color;
for (auto& v : g[u])
if (colorMap[v] == UNSEEN)
KosarajuDFS(g, v, S, colorMap, color);
S.push_back(u);
}
// Compute the number of SCCs and maps nodes to their corresponding SCCs.
// input: directed graph (g[u] contains the neighbors of u, nodes are named 0,1,...,|V|-1).
// output: the number of SCCs (return value), a mapping from node to SCC color (components).
// time: O(V+E).
int findSCC(const vvi& g, vi& components) {
// first pass: record the `post-order' of original graph
vi postOrder, seen;
seen.assign(g.size(), UNSEEN);
for (int i = 0; i < g.size(); ++i)
if (seen[i] == UNSEEN)
KosarajuDFS(g, i, postOrder, seen, SEEN);
// second pass: explore the SCCs based on first pass result
vvi reverse_g(g.size(),vi());
for (int u=0; u<g.size(); u++) for (int v : g[u]) reverse_g[v].push_back(u);
vi dummy;
components.assign(g.size(), UNSEEN);
int numSCC = 0;
for (int i = (int)g.size()-1; i >= 0; --i)
if (components[postOrder[i]] == UNSEEN)
KosarajuDFS(reverse_g, postOrder[i], dummy, components, numSCC++);
return numSCC;
}
// Computes the SCC graph of a given digraph.
// input: directed graph (g[u] contains the neighbors of u, nodes are named 0,1,...,|V|-1).
// output: strongly connected components graph of g (sccg).
// time: O(V+E).
void findSCCgraph(const vvi& g, vsi& sccg) {
vi component;
int n = findSCC(g, component);
sccg.assign(n, si());
for (int u=0; u<g.size(); u++) for (int v: g[u]) // for every edge u->v
if (component[u] != component[v])
sccg[component[u]].insert(component[v]);
}
/********** Shortest Paths **********/
// input: non-negatively weighted directed graph (g[u] contains pairs (v,w) such that u->v has weight w, nodes are named 0,1,...,|V|-1), source (s).
// output: distances from s (dist).
// time: O(ElogV).
void Dijkstra(const vvii& g, int s, vi& dist) {
dist = vi(g.size(), INF);
dist[s] = 0;
priority_queue<ii, vii, greater<ii>> q;
q.push({0, s});
while (!q.empty()) {
ii front = q.top(); q.pop();
int d = front.first, u = front.second;
if (d > dist[u]) continue; // We may have found a shorter way to get to u after inserting it to q.
// In that case, we want to ignore the previous insertion to q.
for (ii next : g[u]) {
int v = next.first, w = next.second;
if (dist[u]+w < dist[v]) {
dist[v] = dist[u]+w;
q.push({dist[v], v});
}
}
}
}
// input: weighted directed graph (g[u] contains pairs (v,w) such that u->v has weight w, nodes are named 0,1,...,|V|-1), source node (s).
// output: is there a negative cycle in g? (return value), the distances from s (d)
// comment: the values in d are valid only if there is no negative cycle.
// time: O(VE).
bool BellmanFord(const vvii& g, int s, vi& d) {
d.assign(g.size(), INF);
d[s] = 0;
bool changed = false;
// V times
for (int i = 0; i < g.size(); ++i) {
changed = false;
// go over all edges u->v with weight w
for (int u = 0; u < g.size(); ++u) for (ii e : g[u]) {
int v = e.first;
int w = e.second;
// relax the edge
if (d[u] < INF && d[u]+w < d[v]) {
d[v] = d[u]+w;
changed = true;
}
}
}
// there is a negative cycle if there were changes in the last iteration
return changed;
}
// input: weighted directed graph (g[u] contains pairs (v,w) such that u->v has weight w, nodes are named 0,1,...,|V|-1).
// output: the pairwise distances (d).
// time: O(V^3).
void FloydWarshall(const vvii& g, vvi& d) {
// initialize distances according to the graph edges
d.assign(g.size(), vi(g.size(), INF));
for (int u=0; u<g.size(); ++u) d[u][u] = 0;
for (int u=0; u<g.size(); ++u) for (ii e: g[u]) {
int v = e.first; int w = e.second;
d[u][v] = min(d[u][v],w);
}
// relax distances using the Floyd-Warshall algorithm
for (int k=0; k<g.size(); ++k)
for (int u=0; u<g.size(); ++u)
for (int v=0; v<g.size(); ++v)
d[u][v] = min(d[u][v], d[u][k]+d[k][v]);
}
/********** Min Spanning Tree **********/
struct unionfind {
vector<int> rank;
vector<int> parent;
unionfind (int size) {
rank=vector<int>(size,0);
parent=vector<int>(size);
for(int i=0;i<size;i++) parent[i]=i;
}
int find(int x) {
int tmp=x;
while(x!=parent[x]) x=parent[x];
while(tmp!=x) {
int remember=parent[tmp];
parent[tmp]=x;
tmp=remember;
}
return x;
}
void unite(int p, int q) {
p = find(p);
q = find(q);
if(q==p) return;
if(rank[p] < rank[q]) parent[p] = q;
else parent[q] = p;
if(rank[p] == rank[q]) rank[p]++;
}
};
// input: edges v1->v2 of the form (weight,(v1,v2)),
// number of nodes (n), all nodes are between 0 and n-1.
// output: weight of a minimum spanning tree.
// time: O(ElogV).
int Kruskal(vector<iii>& edges, int n) {
sort(edges.begin(), edges.end());
int mst_cost = 0;
unionfind components(n);
for (iii e : edges) {
if (components.find(e.second.first) != components.find(e.second.second)) {
mst_cost += e.first;
components.unite(e.second.first, e.second.second);
}
}
return mst_cost;
}
/********** Max Flow **********/
int augment(vvi& res, int s, int t, const vi& p, int minEdge) {
// traverse the path from s to t according to p.
// change the residuals on this path according to the min edge weight along this path.
// return the amount of flow that was added.
if (t == s) {
return minEdge;
} else if (p[t] != -1) {
int f = augment(res, s, p[t], p, min(minEdge, res[p[t]][t]));
res[p[t]][t] -= f;
res[t][p[t]] += f;
return f;
}
return 0;
}
// input: number of nodes (n), all nodes are between 0 and n-1,
// edges v1->v2 of the form (weight,(v1,v2)), source (s) and target (t).
// output: max flow from s to t over the edges.
// time: O(VE^2) and O(EF).
int EdmondsKarp (int n, vector<iii>& edges, int s, int t) {
// initialise adjacenty list and residuals adjacency matrix
vvi res(n,vi(n,0));
vvi adj(n);
for (iii e : edges) {
res[e.second.first][e.second.second] += e.first;
adj[e.second.first].push_back(e.second.second);
adj[e.second.second].push_back(e.second.first);
}
// while we can add flow
int addedFlow, maxFlow = 0;
do {
// save to p the BFS tree from s to t using only edges with residuals
vi dist(res.size(), INF);
dist[s] = 0;
queue<int> q;
q.push(s);
vi p(res.size(), -1);
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == t) break;
for (int v : adj[u]) if (res[u][v] > 0 && dist[v] == INF) {
dist[v] = dist[u] + 1;
q.push(v);
p[v] = u;
}
}
// add flow on the path between s to t according to p
addedFlow = augment(res, s, t, p, INF);
maxFlow += addedFlow;
} while (addedFlow > 0);
return maxFlow;
}
void fillPossibilities(vector<vector<long long>>& possibilities, long long R, long long N, long long M, int i, int j){
if(i > N)
return; // out of bounds
if(j > N)
return fillPossibilities(possibilities, R,N,M, i+1,0); // go to next row
if(possibilities[i][j] != 0)
return fillPossibilities(possibilities, R, N, M, i, j+1);
if(i == 1){
possibilities[i][j] = 0;
return fillPossibilities(possibilities, R, N, M, i, j+1);
}
if(i == R) { // we don't want to count this
possibilities[i][j] = possibilities[i - 1][j - 1];
return fillPossibilities(possibilities, R, N, M, i, j+1);
}
bool flag = false;
if(j > 1){
possibilities[i][j] = possibilities[i-1][j-1] % M;
flag = true;
}
if(flag)
possibilities[i][j] = (possibilities[i][j] + (j * possibilities[i-1][j])) % M;
else possibilities[i][j] = (j * possibilities[i-1][j]) % M;
if(j < N){
possibilities[i][j] = (possibilities[i][j] + ((j * (j+1)/2) * possibilities[i-1][j+1])) % M;
}
fillPossibilities(possibilities, R, N, M, i, j+1);
}
int main(){
long long R, N, M;
cin >> R >> N >> M;
vector<vector<long long>> possibilities(N+1, vector<long long>(N+1));
possibilities[1][1] = 1;
fillPossibilities(possibilities, R, N, M, 1, 1);
cout << possibilities[N][1] << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3672kb
input:
1 14 123456789
output:
75904192
result:
ok single line: '75904192'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
7 14 123456789
output:
72179669
result:
ok single line: '72179669'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
13 14 123456789
output:
2702765
result:
ok single line: '2702765'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
14 14 123456789
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
25 50 123456789
output:
65438273
result:
ok single line: '65438273'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3700kb
input:
25 50 123456788
output:
77049037
result:
ok single line: '77049037'
Test #7:
score: 0
Accepted
time: 131ms
memory: 35224kb
input:
1010 2021 999999883
output:
356413310
result:
ok single line: '356413310'
Test #8:
score: 0
Accepted
time: 131ms
memory: 35216kb
input:
1 2021 999999937
output:
141524412
result:
ok single line: '141524412'
Test #9:
score: 0
Accepted
time: 129ms
memory: 35216kb
input:
5 2021 999999929
output:
833185836
result:
ok single line: '833185836'
Test #10:
score: 0
Accepted
time: 125ms
memory: 35128kb
input:
2017 2021 999999797
output:
503659284
result:
ok single line: '503659284'
Test #11:
score: 0
Accepted
time: 125ms
memory: 35108kb
input:
2021 2021 999999751
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 61ms
memory: 19084kb
input:
271 1414 314159265
output:
66534359
result:
ok single line: '66534359'