Submission #51655

#	Time	Username	Problem	Language	Result	Execution time	Memory
51655		gs13105	Rope (JOI17_rope)	C++17	100 / 100	2257 ms	141776 KiB

rope

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

inline int bs_count(vector<int> &v, int x)
{
    auto p = equal_range(v.begin(), v.end(), x);
    return p.second - p.first;
}

int arr[1000010];
int res[1000010];
int n, m;

void solve(int s)
{
    vector<int> cnt(m + 1);
    vector<vector<int>> adj(m + 1);
    for(int i = s; i <= n; i += 2)
    {
        int x = arr[i];
        int y = arr[i + 1];

        cnt[x]++;
        cnt[y]++;
        if(x && y && x != y)
        {
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    for(int i = 1; i <= m; i++)
        sort(adj[i].begin(), adj[i].end());

    vector<pair<int, int>> sor;
    for(int i = 1; i <= m; i++)
        sor.push_back({ cnt[i], i });
    sort(sor.rbegin(), sor.rend());

    for(int i = 1; i <= m; i++)
    {
        priority_queue<int> pq;
        pq.push(0);

        for(auto &p : sor)
        {
            int c, y;
            tie(c, y) = p;

            if(y == i)
                continue;

            int t = bs_count(adj[i], y);
            pq.push(c - t);
            if(t == 0)
                break;
        }

        int r = n - cnt[i] - pq.top();
        res[i] = min(r, res[i]);
    }
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);

    arr[0] = arr[n + 1] = 0;

    for(int i = 1; i <= m; i++)
        res[i] = n;

    solve(0);
    solve(1);

    for(int i = 1; i <= m; i++)
        printf("%d\n", res[i]);
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20