| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1120072 | dowdow | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <stack>
#include <climits>
using namespace std;
class Graph {
public:
int V; // Number of vertices
vector<vector< pair<uint, uint>>> adj; // adjacency list (pair of vertex and weight)
Graph(int V) {
this->V = V;
adj.resize(V+1); // Vertex starts from 1 to V, skip index 0
}
// Add an edge from u to v with weight w
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
}
// Helper function for topological sort using DFS
void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& topoStack) {
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
for (auto& neighbor : adj[v]) {
int u = neighbor.first;
if (!visited[u]) {
topologicalSortUtil(u, visited, topoStack);
}
}
// Push current vertex to stack after visiting all its neighbors
topoStack.push(v);
}
// Function to perform topological sort
stack<int> topologicalSort() {
vector<bool> visited(V, false);
stack<int> topoStack;
// Perform DFS for all unvisited vertices
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topologicalSortUtil(i, visited, topoStack);
}
}
return topoStack;
}
// Function to find the longest path in the DAG
int longestPath(int src, const set<uint>& unattended) {
// stack<int> topoStack = topologicalSort();
// cout << src << endl;
// Initialize distances to all vertices as negative infinity
vector<int> dist(V, INT_MIN);
dist[src] = 0; // Distance to the source is 0
// Process vertices in topological order from src and above
//while (!topoStack.empty()) {
// int u = topoStack.top();
// topoStack.pop();
for (int i = src; i > 0; i--) {
int u = i;
// cout << u << endl;
// Update distances for all adjacent vertices of u
if (dist[u] != INT_MIN) {
for (auto& neighbor : adj[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (neighbor.first > src) {
continue;
}
// cout << "Neighbor" << v << " weight: " << weight<< endl;
if (dist[u] + weight > dist[v]) {
dist[v] = dist[u] + weight;
// cout << "distance[v]: " << dist[v] << endl;
}
}
}
}
// Find the longest path
int max_dist = -1;
for (int i = 1; i <= src; i++) {
// cout << i << endl;
// cout << "unattended size: " << unattended.size() << endl;
if (unattended.find(i) != unattended.end()) {
// cout << "unattended: " << i << endl;
continue;
}
if (dist[i] > max_dist) {
max_dist = dist[i];
}
}
// cout << "max_dist: " << max_dist << endl;
return max_dist;
}
};
class Gathering {
public:
uint Town;
uint number; // # of beavers couldn't come
set<uint> beavers; // beavers couldn't come
int max_path; // longest canal for beavers could come
Gathering(uint T, uint number) {
this->Town = T;
this->number = number;
this->max_path = -1;
}
Gathering(const Gathering& G) {
this->Town = G.Town;
this->number = G.number;
this->max_path = G.max_path;
this->beavers = G.beavers;
// cout << " copy constructor: " << this->beavers.size() << " input: " << G.beavers.size() << endl;
}
void addBeaver(uint beaver) {
beavers.insert(beaver);
}
};
class Node {
public:
int value;
vector<pair<int, int>> *multi;
Node(int value) {
this->value = value;
}
vector<pair<int, int>>* pairs() {
return multi;
}
};
class Matrix {
private:
int rows;
int cols;
std::vector<std::vector<Node*>> data;
// std::vector<std::pair<int, int>> multi; // a set of multiples
public:
// Constructor to initialize a matrix with given rows and columns, and optionally fill with a value
Matrix(int r, int c) : rows(r), cols(c) {}
// Copy constructor to create a deep copy of another matrix
Matrix(const Matrix& other) : rows(other.rows), cols(other.cols), data(other.data) {}
// Accessor for rows and columns
int getRows() const { return rows; }
int getCols() const { return cols; }
// Element access (with bounds checking)
Node *at(int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) {
throw std::out_of_range("Index out of bounds");
}
return data[r][c];
}
// Set data
void set_at(int r, int c, Node* node) {
if (r < 0 || r >= rows || c < 0 || c >= cols) {
throw std::out_of_range("Index out of bounds");
}
data[r][c] = node;
}
// Display the matrix
void display() const {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
std::cout << data[i][j]->value << " ";
}
std::cout << std::endl;
}
}
};
int main() {
uint R = 0;
uint S = 0;
uint N = 0;
cin >> R >> S >> N;
// Add edges: (from, to, weight)
Matrix matrix(R,S); // Create a matrix with R*S
for(int i = 0; i < R; i++) {
for(int j = 0; j < S; j++) {
uint value = 0;
cin >> value;
Node *node = new Node(value);
matrix.set_at(i, j, node);
}
}
for(int i = S; i > 0; i--) {
for(int j = R; j > 0; j--) {
Node *node = matrix.at(i,j);
if (i < S) {
Node *right_node = matrix.at(i+1, j);
for (auto& multi: right_node->pairs()) {
node->multi.push_back(right_node->pairs());
node->multi.push_back({i+1, right_node->value});
}
}
if (j < R) {
Node *down_node = matrix.at(i,j+1);
}
for (int k = 0; node->multi.size(); k++) {
}
}
}
return 0;
}