Submission #1120073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120073		dowdow	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2058 ms	23612 KiB

bitaro

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

int main() {
  uint N = 0;
  uint M = 0;
  uint Q = 0;
  cin >> N >> M >> Q;

   // Add edges: (from, to, weight)
  Graph canals(N);  // Create a graph with N vertices
  for(int i = 0; i < M; i++) {
    uint T = 0;
    uint S = 0;
    cin >> T >> S;
    canals.addEdge(S, T, 1);
    //cout << T << "  "  << S << endl;
  }

  // Input the gathering
  vector<Gathering*> gathering;
  for (int i = 0; i < Q; i++) {
    uint a, b;
    cin >> a >> b;
    Gathering *G = new Gathering(a, b);
    gathering.push_back(G);
    for (int j = 0; j < b; j++) {
      uint beaver; 
      cin >> beaver;
      G->addBeaver(beaver);
    }
    // cout << "beaver size: " << G->beavers.size() << endl;
  }
  // cout << "finish input" << endl;
  // Find the longest path for each beaver
  for (auto& G : gathering) {
      // Find the longest path from the source vertex at each gathering
      // cout << "G.beavers.size(): " << G->beavers.size() << " " << G->number << endl;
      int dist = canals.longestPath(G->Town, G->beavers);
      // Output: for each gathering, output the longest path
      cout << dist << endl;
  }

  return 0;
}

Compilation message (stderr)

bitaro.cpp: In member function 'int Graph::longestPath(int, const std::set<unsigned int>&)':
bitaro.cpp:75:40: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   75 |                     if (neighbor.first > src) {
      |                         ~~~~~~~~~~~~~~~^~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'uint' {aka 'unsigned int'} [-Wsign-compare]
  141 |   for(int i = 0; i < M; i++) {
      |                  ~~^~~
bitaro.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'uint' {aka 'unsigned int'} [-Wsign-compare]
  151 |   for (int i = 0; i < Q; i++) {
      |                   ~~^~~
bitaro.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'uint' {aka 'unsigned int'} [-Wsign-compare]
  156 |     for (int j = 0; j < b; j++) {
      |                     ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86