oj.uz

Submission #305095

# Submission time Handle Problem Language Result Execution time Memory
305095 2020-09-22T15:03:34 Z phathnv Teoretičar (COCI18_teoreticar) C++11
130 / 130
 5066 ms 117672 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6016 KB Output is correct
2 Correct 15 ms 6144 KB Output is correct
3 Correct 17 ms 6272 KB Output is correct
4 Correct 9 ms 5632 KB Output is correct
5 Correct 9 ms 5504 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5760 KB Output is correct
2 Correct 15 ms 6144 KB Output is correct
3 Correct 17 ms 6400 KB Output is correct
4 Correct 12 ms 5760 KB Output is correct
5 Correct 9 ms 5504 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 57912 KB Output is correct
2 Correct 4613 ms 99324 KB Output is correct
3 Correct 2119 ms 84728 KB Output is correct
4 Correct 1171 ms 59468 KB Output is correct
5 Correct 1077 ms 50404 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 57016 KB Output is correct
2 Correct 2161 ms 84612 KB Output is correct
3 Correct 3112 ms 113312 KB Output is correct
4 Correct 1187 ms 61240 KB Output is correct
5 Correct 283 ms 18644 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3208 ms 76312 KB Output is correct
2 Correct 3681 ms 98144 KB Output is correct
3 Correct 191 ms 17380 KB Output is correct
4 Correct 1608 ms 64660 KB Output is correct
5 Correct 367 ms 31496 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2100 ms 72920 KB Output is correct
2 Correct 4751 ms 98184 KB Output is correct
3 Correct 3447 ms 117672 KB Output is correct
4 Correct 1796 ms 68916 KB Output is correct
5 Correct 1191 ms 61112 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1851 ms 60252 KB Output is correct
2 Correct 5066 ms 98368 KB Output is correct
3 Correct 4244 ms 99504 KB Output is correct
4 Correct 1839 ms 69084 KB Output is correct
5 Correct 1649 ms 63284 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 60048 KB Output is correct
2 Correct 5048 ms 99116 KB Output is correct
3 Correct 3315 ms 103528 KB Output is correct
4 Correct 378 ms 21100 KB Output is correct
5 Correct 1625 ms 63788 KB Output is correct