Submission #305095

#	Time	Username	Problem	Language	Result	Execution time	Memory
305095		phathnv	Teoretičar (COCI18_teoreticar)	C++11	130 / 130	5066 ms	117672 KiB

teoreticar

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Teoretica"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 10;
const int M = 5e5 + 10;

struct edge{
    int l, r;
    edge(int _l = 0, int _r = 0){
        l = _l;
        r = _r;
    }
};

struct dataT{
    int nxt, idx;
    dataT(int _nxt = 0, int _idx = 0){
        nxt = _nxt;
        idx = _idx;
    }
};

int m;
vector <edge> edges;

vector <dataT> adj[2 * N];
int col[M + 2 * N], curCol;
bool vst[M + 2 * N];

void readInput(){
    int tmp;
    scanf("%d %d %d", &tmp, &tmp, &m);
    edges.resize(m);
    for(int i = 0; i < m; i++)
        scanf("%d %d", &edges[i].l, &edges[i].r);
}

void color(int u){
    while (!adj[u].empty()){
        dataT d = adj[u].back();
        adj[u].pop_back();
        if (vst[d.idx])
            continue;
        vst[d.idx] = 1;
        color(d.nxt);
        col[d.idx] = curCol;
        curCol ^= 1;
    }
}

vector <int> calc(vector <edge> edges){
//    cerr << "calc " << endl;
//    for(edge e : edges)
//        cerr << e.l << ' ' << e.r << endl;


    if (edges.empty())
        return vector<int>(0);

    vector <int> cL, cR;
    for(edge e : edges){
        cL.push_back(e.l);
        cR.push_back(e.r);
    }
    sort(cL.begin(), cL.end());
    sort(cR.begin(), cR.end());
    cL.resize(unique(cL.begin(), cL.end()) - cL.begin());
    cR.resize(unique(cR.begin(), cR.end()) - cR.begin());
    int nL = cL.size() + 1;
    int nR = cR.size() + 1;

    for(int i = 0; i < nL + nR; i++)
        adj[i].clear();

    int cntEdge = 0;
    for(edge e : edges){
        int l = lower_bound(cL.begin(), cL.end(), e.l) - cL.begin();
        int r = lower_bound(cR.begin(), cR.end(), e.r) - cR.begin();
        adj[l].push_back(dataT(nL + r, cntEdge));
        adj[nL + r].push_back(dataT(l, cntEdge));
        //cerr << "addEdge " << l << ' ' << r << endl;
        cntEdge++;
    }

//    cerr << nL << ' ' << nR << endl;
//    for(int i = 0; i < nL + nR; i++)
//        cerr << "vex " << i << ' ' << adj[i].size() << endl;

    bool ok = 1;
    for(int i = 0; i < nL + nR; i++)
        if ((int) adj[i].size() > 1){
            ok = 0;
            break;
        }
    if (ok)
        return vector<int>((int) edges.size(), 0);

    for(int i = 0; i < nL - 1; i++)
        if ((int) adj[i].size() % 2){
            adj[i].push_back(dataT(nL + nR - 1, cntEdge));
            adj[nL + nR - 1].push_back(dataT(i, cntEdge));
            //cerr << "addEdge " << i << ' ' << nR - 1 << endl;
            cntEdge++;
        }
    for(int i = nL; i < nL + nR - 1; i++)
        if ((int) adj[i].size() % 2){
            adj[i].push_back(dataT(nL - 1, cntEdge));
            adj[nL - 1].push_back(dataT(i, cntEdge));
            //cerr << "addEdge " << nL - 1 << ' ' << i - nL << endl;
            cntEdge++;
        }
    if ((int) adj[nL - 1].size() % 2){
        adj[nL + nR - 1].push_back(dataT(nL - 1, cntEdge));
        adj[nL - 1].push_back(dataT(nL + nR - 1, cntEdge));
        //cerr << "addEdge " << nL - 1 << ' ' << nR - 1 << endl;
        cntEdge++;
    }

    for(int i = 0; i < cntEdge; i++)
        vst[i] = 0;
    for(int i = 0; i < nL + nR; i++)
        color(i);
    for(int i = 0; i < cntEdge; i++)
        assert(vst[i]);


    vector <edge> toL, toR;
    vector <int> cols;
    for(int i = 0; i < (int) edges.size(); i++){
        if (col[i])
            toL.push_back(edges[i]);
        else
            toR.push_back(edges[i]);
        cols.push_back(col[i]);
    }

    assert(!toL.empty());
    assert(!toR.empty());

    vector <int> resL = calc(toL);
    vector <int> resR = calc(toR);

    assert(resL.size() == toL.size());
    assert(resR.size() == toR.size());

    vector <int> res;
    int shift = *max_element(resL.begin(), resL.end()) + 1;
    int ptrL = 0, ptrR = 0;
    for(int c : cols)
        if (c)
            res.push_back(resL[ptrL++]);
        else
            res.push_back(shift + resR[ptrR++]);

    assert(res.size() == edges.size());

//    cerr << "cntEdge " << cntEdge << endl;
//    for(int i = 0; i < cntEdge; i++)
//        cerr << col[i] << endl;

    return res;
}

void solve(){
    vector <int> res = calc(edges);
    printf("%d\n", *max_element(res.begin(), res.end()) + 1);
    for(int c : res)
        printf("%d\n", c + 1);
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

teoreticar.cpp: In function 'void readInput()':
teoreticar.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d %d %d", &tmp, &tmp, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%d %d", &edges[i].l, &edges[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13