Submission #93544

#	Time	Username	Problem	Language	Result	Execution time	Memory
93544		ajmasin	Pictionary (COCI18_pictionary)	C++14	140 / 140	223 ms	28664 KiB

pictionary

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14