oj.uz

Submission #370733

# Submission time Handle Problem Language Result Execution time Memory
370733 2021-02-24T14:14:07 Z aZvezda Teoretičar (COCI18_teoreticar) C++14
52 / 130
 12000 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 5e5 + 10;
bool in[MAX_N], used[MAX_N];
vector<pair<int, int> > g[MAX_N];
int finalColours[MAX_N];
int l, r, m;
bool gotThrough[MAX_N];

void dfs(int x, bool flag) {
    gotThrough[x] = true;
    for(auto it : g[x]) {
        if(!used[it.second]) {
            used[it.second] = true;
            in[it.second] = flag;
            dfs(it.first, flag ^ 1);
        }
    }
}

int solve(vector<pair<pair<int, int>, int> > &edges) {
    vector<int> active;
    for(auto it : edges) {
        g[it.first.first].resize(0);
        g[it.first.second].resize(0);
    }
    for(auto it : edges) {
        active.push_back(it.first.first);
        active.push_back(it.first.second);
        used[it.second] = false;
        g[it.first.first].push_back({it.first.second, it.second});
        gotThrough[it.first.first] = false;
        gotThrough[it.first.second] = false;
        g[it.first.second].push_back({it.first.first, it.second});
    }
    sort(active.begin(), active.end());
    active.resize(unique(active.begin(), active.end()) - active.begin());
    bool allOne = true;
    for(auto it : active) {
        if(g[it].size() > 1) {
            allOne = false;
            break;
        }
    }
    if(allOne) {
        for(auto it : edges) {
            finalColours[it.second] = 1;
        }
        return 1;
    }
    g[l + r + 1].resize(0);
    g[l + r + 2].resize(0);
    int cnt = m;
    for(auto it : active) {
        if(g[it].size() & 1) {
            if(it <= l) {
                g[l + r + 1].push_back({it, cnt});
                g[it].push_back({l + r + 1, cnt});
            } else {
                g[l + r + 2].push_back({it, cnt});
                g[it].push_back({l + r + 2, cnt});
            }
            used[cnt] = false;
            cnt ++;
        }
    }
    if(g[l + r + 1].size() & 1) {
        g[l + r + 1].push_back({l + r + 2, cnt});
        g[l + r + 2].push_back({l + r + 1, cnt});
        used[cnt] = false;
    }
    for(int i = 0; i <= l + r + 2; i ++) {
        for(auto it : g[i]) {
            if(i > it.first) {continue;}
        }
    }
    for(auto it : active) {
        if(!gotThrough[it]) {
            dfs(it, 0);
        }
    }
    vector<pair<pair<int, int>, int> > lft, rght;
    for(auto it : edges) {
        if(in[it.second]) {
            lft.push_back(it);
        } else {
            rght.push_back(it);
        }
    }
    int lftAns = solve(lft), rghtAns = solve(rght);
    for(auto it : rght) {
        finalColours[it.second] += lftAns;
    }
    return lftAns + rghtAns;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> l >> r >> m;
    vector<pair<pair<int, int>, int> > edges;
    for(int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({{a, b + l}, i});
    }
    int ret = solve(edges);
    cout << ret << endl;
    for(int i = 0; i < m; i ++) {
        cout << finalColours[i] << endl;
    }
    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 13168 KB Output is correct
2 Correct 22 ms 13036 KB Output is correct
3 Correct 40 ms 13292 KB Output is correct
4 Correct 12 ms 12780 KB Output is correct
5 Correct 13 ms 12928 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13036 KB Output is correct
2 Correct 22 ms 13036 KB Output is correct
3 Correct 41 ms 13420 KB Output is correct
4 Correct 14 ms 12908 KB Output is correct
5 Correct 13 ms 12684 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2019 ms 67616 KB Output is correct
2 Runtime error 1727 ms 144848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2032 ms 68304 KB Output is correct
2 Runtime error 1506 ms 142816 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2945 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5560 ms 69480 KB Output is correct
2 Runtime error 2324 ms 138968 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5679 ms 69500 KB Output is correct
2 Runtime error 2839 ms 138592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -