Submission #834082

#	Time	Username	Problem	Language	Result	Execution time	Memory
834082		HollaFoil	Arcade (NOI20_arcade)	C++14	30 / 100	6 ms	1108 KiB

Arcade

#include <bits/stdc++.h>
using namespace std;

#define V 302
int m;

bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
    bool visited[V];
    memset(visited, 0, sizeof(visited));
 
    queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        for (int v = 0; v < 2*m+2; v++) {
            if (visited[v] == false && rGraph[u][v] > 0) {
                if (v == t) {
                    parent[v] = u;
                    return true;
                }
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
 
    return false;
}

int fordFulkerson(int graph[V][V], int s, int t) {
    int u, v;
    int rGraph[V][V];
    for (u = 0; u < 2*m+2; u++)
        for (v = 0; v < 2*m+2; v++)
            rGraph[u][v] = graph[u][v];
 
    int parent[V];
 
    int max_flow = 0; 
    while (bfs(rGraph, s, t, parent)) {
        int path_flow = INT_MAX;
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }
        max_flow += path_flow;
    }
     return max_flow;
}

int main() {
    int n;
    cin >> n >> m;
    vector<int> timesold(m+1);
    vector<int> locationsold(m+1);
    for (int i = 0; i < m; i++) cin >> timesold[i+1];
    for (int i = 0; i < m; i++) cin >> locationsold[i+1];
    vector<int> times;
    vector<int> locations;
    times.push_back(0);
    locations.push_back(0);
    for (int i = 1; i < m+1; i++) {
        bool valid = true;
        for (int j = i+1; j < m+1; j++) {
            if (timesold[i] != timesold[j] || locationsold[i] != locationsold[j]) continue;
            valid = false;
            break;
        }
        if (valid) times.push_back(timesold[i]);
        if (valid) locations.push_back(locationsold[i]);
    }
    m = times.size()-1;


    int graph[V][V];
    for (int i = 0; i < 2*m+2; i++) {
        for (int j = 0; j < 2*m+2; j++) {
            graph[i][j] = 0;
        }
    }
    for (int i = 1; i < m+1; i++) {
        graph[0][i] = 1;
        graph[i+m][2*m+1] = 1;
    }
    for (int i = 1; i < m+1; i++) {
        for (int j = 1; j < m+1; j++) {
            if (i == j) continue;
            else if (times[i] > times[j]) continue;
            else if (times[j]-times[i] < abs(locations[i]-locations[j])) continue;
            else graph[i][j+m] = 1;
        }
    }
    cout << m - fordFulkerson(graph, 0, 2*m+1) << endl;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15