oj.uz

Submission #347735

# Submission time Handle Problem Language Result Execution time Memory
347735 2021-01-13T10:50:36 Z Harry464 Pictionary (COCI18_pictionary) C++14
14 / 140
 1500 ms 9156 KB 
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n, m, q;
    cin >> n >> m >> q;
    vector <pair <ll, ll>> kv(q);
    for (int i = 0; i < q; i++)
        cin >> kv[i].first >> kv[i].second;
    vector <ll> lo(q, 1);
    vector <ll> hi(q, m + 1);
    vector <ll> rjesenja(q, -1);
    vector <ll> ranks(n,0);
    ll rjeseni = 0;
    while (rjeseni < q){
        vector <pair <ll,ll>> mids(q);
        for (int i = 0; i < q; i++)
            mids[i].first = (lo[i]+hi[i])/2, mids[i].second = i;
        sort(mids.begin(), mids.end());
        vector <ll> par(n);
        for (int i = 0; i < n; i++)
            par[i] = i;
        ll slid = 0;
        for (int i = 0; i < m; i++){
            ll tren = 2*(m - i);
            while (tren <= n){
                ll part = tren-1;
                while (part != par[part])
                    part = par[part];
                ll pars = m - i - 1;
                while (pars != par[pars])
                    pars = par[pars];
                if (pars == part){
                    tren += m - i;
                    continue;
                }
                if (ranks[pars] < ranks[part])
                    swap(pars,part);
                par[part] = pars;
                if (ranks[pars] == ranks[part]) ranks[pars]++;
                tren += m - i;
            }
            while (slid <= n && mids[slid].first == i + 1){
                ll upit = mids[slid].second;
                if (rjesenja[upit] != -1){
                    slid++;
                    continue;
                }
                ll para = kv[upit].first-1, parb = kv[upit].second-1;
                while (para != par[para])
                    para = par[para];
                while (parb != par[parb])
                    parb = par[parb];
                if (para == parb){
                    hi[upit] = i + 1;
                } else {
                   lo[upit] = i + 2;
                }
                if (lo[upit] >= hi[upit]){
                    rjeseni++, rjesenja[upit] = lo[upit];
                }
                slid++;
            }
        }
    }
    for (int i = 0; i < q; i++)
        cout << rjesenja[i] << endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 620 KB Time limit exceeded

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 1388 KB Time limit exceeded

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 4076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 5868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 3160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 3460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1540 ms 4724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1581 ms 6084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1555 ms 6428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 7996 KB Output is correct
2 Correct 675 ms 9156 KB Output is correct