oj.uz

답안 #90360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90360 2018-12-21T10:51:38 Z Alexa2001 Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 6 ms 5228 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

priority_queue<int> heap;
int start[Nmax], finish[Nmax], add[Nmax], dp[Nmax], s[Nmax];
vector<int> v[Nmax];
int n, m, i, A, B;
vector< pair<int,int> > edges;

int mod(int x)
{
    if(x <= 0) return x+n;
    if(x>n) return x-n;
    return x;
}

bool check_center(int where, int L)
{
    int i, need = 0, nr;

    for(i=1; i<=n; ++i) v[i].clear();

    for(auto e : edges)
    {
        int x, y;
        x = mod(e.first - where + 1);
        y = mod(e.second - where + 1);

        if(x > y) swap(x, y);
        v[x].push_back(y);
    }

    while(heap.size()) heap.pop();

    for(i=1; i<=n; ++i) finish[i] = 0;

    for(i=1; i<=n; ++i)
    {
        start[i] = v[i].size(); add[i] = 0;
        for(auto it : v[i]) finish[it] ++;
    }

    dp[0] = L;
    for(i=1; i<n; ++i)
    {
        for(auto it : v[i]) heap.push(it);

        dp[i] = dp[i-1] + start[i] - finish[i] + add[i];

        while(dp[i] > L && need <= L)
        {
            assert(heap.size());

            dp[i] -= 2;
            nr = heap.top();
            heap.pop();
            add[nr] += 2;
            ++need;
        }

        if(need > L) return 0;
    }

    return (need <= L);
}

bool check(int L)
{
    int i;
    for(i=1; i<=n; ++i)
        return (check_center(A, L) || check_center(B, L));
}

int best_point(bool dir)
{
    int i;
    for(i=1; i<=n; ++i)
        s[i] = 0;

    for(auto e : edges)
        if(dir == 0)
        {
            ++s[e.first];
            --s[e.second];
        }
        else
        {
            ++s[e.second];
            ++s[1];
            --s[e.first];
        }

    for(i=1; i<=n; ++i) s[i] += s[i-1];

    int Max = 0;
    for(i=1; i<=n; ++i) Max = max(Max, s[i]);
    for(i=1; i<=n; ++i)
        if(Max == s[i]) return mod(i-1);
}

int main()
{
 //   freopen("input", "r", stdin);

    cin >> n >> m;

    int i, x, y, C;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> C;
        if(x > y) swap(x, y);
        edges.push_back({x, y});
    }

    A = best_point(0);
    B = best_point(1);

    int st = 0, dr = m, mid;
    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(check(mid)) dr = mid - 1;
            else st = mid + 1;
    }

    cout << st << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Incorrect 5 ms 5228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Incorrect 5 ms 5228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Incorrect 5 ms 5228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Incorrect 5 ms 5228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Incorrect 5 ms 5228 KB Output isn't correct
9 Halted 0 ms 0 KB -