oj.uz

Submission #93544

# Submission time Handle Problem Language Result Execution time Memory
93544 2019-01-09T12:44:39 Z ajmasin Pictionary (COCI18_pictionary) C++14
140 / 140
 223 ms 28664 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)

const int maxn = 100100;

int n, m, q;

int rj[maxn];

struct query
{
    int a, b;
    int ind;
    query(int _a, int _b, int _ind)
    {
        a = _a;
        b = _b;
        ind = _ind;
    }
    query(){}
}ovaj;

struct zad
{
    int tko, vel;
    zad(int _tko, int _vel)
    {
        tko = _tko;
        vel = _vel;
    }
    zad(){}
};

int rod[maxn];
int vel[maxn];

vector <zad> stek;

vector <query> upis;

int dajrod(int cvor)
{
    if(rod[cvor] == cvor) return cvor;
    return dajrod(rod[cvor]);
}

void spoji(int a, int b)
{
    int ra = dajrod(a), rb = dajrod(b);
    if(vel[ra] > vel[rb]) swap(ra, rb);
    rod[ra] = rb;
    stek.push_back(zad(ra, vel[rb]));
    if(vel[ra] == vel[rb]) vel[rb]++;
    return;
}

void vrati()
{
    zad sad = stek.back();
    stek.pop_back();
    vel[rod[sad.tko]] = sad.vel;
    rod[sad.tko] = sad.tko;
    return;
}

void rijesi(vector <query> tr, int l, int r)
{
    if(r < l) return;
    if(l == r)
    {
        REP(i, 0, (int)tr.size())
        {
            rj[tr[i].ind] = l;
        }
        return;
    }
    int mid = (l + r) / 2;
    REP(i, l, mid + 1)
    {
        for(int j = 2 * (m - i); j <= n; j += (m - i))
        {
            spoji(j - 1, j - (m - i) - 1);
        }
    }
    vector <query> manje, vece;
    REP(i, 0, (int)tr.size())
    {
        ovaj = tr[i];
        if(dajrod(ovaj.a) == dajrod(ovaj.b))
        {
            manje.push_back(ovaj);
        }
        else
        {
            vece.push_back(ovaj);
        }
    }
    rijesi(vece, mid + 1, r);
    REP(i, l, mid + 1)
    {
        for(int j = 2 * (m - i); j <= n; j += (m - i))
        {
            vrati();
        }
    }
    rijesi(manje, l, mid);
    return;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    REP(i, 0, n) {rod[i] = i; vel[i] = 1;}
    int a, b;
    REP(i, 0, q)
    {
        scanf("%d%d", &a, &b);
        a--; b--;
        upis.push_back(query(a, b, i));
    }
    rijesi(upis, 0, m - 1);
    REP(i, 0, q)
    {
        printf("%d\n", rj[i] + 1);
    }
    return 0;
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13780 KB Output is correct
2 Correct 35 ms 9292 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18076 KB Output is correct
2 Correct 52 ms 14360 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 10600 KB Output is correct
2 Correct 57 ms 9320 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 12900 KB Output is correct
2 Correct 53 ms 8936 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 16868 KB Output is correct
2 Correct 87 ms 11328 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12520 KB Output is correct
2 Correct 154 ms 21900 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 24600 KB Output is correct
2 Correct 191 ms 21704 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 28664 KB Output is correct
2 Correct 213 ms 23976 KB Output is correct