oj.uz

Submission #789667

# Submission time Handle Problem Language Result Execution time Memory
789667 2023-07-21T17:10:21 Z Piokemon Teoretičar (COCI18_teoreticar) C++17
130 / 130
 5467 ms 127072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 1e5;
constexpr int M = 5e5;
constexpr int K = 18;
struct kraw{
    int nr;
    int a;
    int b;
};
vector<kraw> krawedzie[(1<<K)+9];
bool zmien[M+9];
int deg[2*N+9];
vector<pair<int,int>> graf[2*N+9];
int gdzie[M+9];
int odp[M+9];
bool bylo[M+9];
bool bylo2[2*N+9];
int ter;

void dfs(int v){
    while(!graf[v].empty()){
        pair<int,int> temp = graf[v].back(); graf[v].pop_back();
        if (temp.second >= 0){
            if (bylo[temp.second]) continue;
            bylo[temp.second] = 1;
        }
        else{
            if (bylo2[-temp.second]) continue;
            bylo2[-temp.second] = 1;
        }
        dfs(temp.first);
        if (temp.second>=0) gdzie[temp.second] = ter%2;
        ter++;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int l,r,m,a,b;
    cin >> l >> r >> m;
    for (int x=0;x<m;x++){
        cin >> a >> b;
        b += l;
        kraw temp; temp.nr = x; temp.a = a; temp.b = b;
        krawedzie[0].push_back(temp);
    }
    set<int> sed;
    vector<int> ind;
    int pot=0;
    for (int k=0;k<K;k++){
        bool ok=1;
        for (int kol=0;kol<(1<<k);kol++){
            for (kraw x:krawedzie[kol]){
                deg[x.a] = 0; deg[x.b] = 0;
            }
            for (kraw x:krawedzie[kol]){
                deg[x.a]++; deg[x.b]++;
            }
            for (kraw x:krawedzie[kol]){
                if (deg[x.a]>1 || deg[x.b]>1){
                    ok = 0;
                    break;
                }
            }
        }
        if (ok){
            pot = k;
            break;
        }
        for (int kol=0;kol<(1<<k);kol++){
            if (krawedzie[kol].empty()) continue;
            sed.clear();
            for (int x=0;x<krawedzie[kol].size();x++){
                sed.insert(krawedzie[kol][x].a);
                sed.insert(krawedzie[kol][x].b);
            }
            ind.clear();
            for (int x:sed){ 
                ind.push_back(x);
                deg[x] = 0;
                graf[x].clear();
            }
            for (kraw x:krawedzie[kol]){
                zmien[x.nr] = 0;
                deg[x.a]++;
                deg[x.b]++;
                graf[x.a].push_back({x.b,x.nr});
                graf[x.b].push_back({x.a,x.nr});
                bylo[x.nr] = 0;
            }
            graf[l+r+1].clear(); deg[l+r+1] = 0;
            graf[l+r+2].clear(); deg[l+r+2] = 0;
            int numer=1;
            for (int x:ind){
                if (deg[x]%2==1){
                    if (x<=l){
                        graf[l+r+2].push_back({x,-numer});
                        graf[x].push_back({l+r+2,-numer});
                        deg[x]++;
                        deg[l+r+2]++;
                        numer++;
                    }
                    else{
                        graf[l+r+1].push_back({x,-numer});
                        graf[x].push_back({l+r+1,-numer});
                        deg[x]++;
                        deg[l+r+1]++;
                        numer++;
                    }
                }
            }
            if (deg[l+r+1]%2==1){
                graf[l+r+2].push_back({l+r+1,-numer});
                graf[l+r+1].push_back({l+r+2,-numer});
                deg[l+r+1]++;
                deg[l+r+2]++;
                numer++;
            }
            for (int x=0;x<=numer;x++) bylo2[x] = 0;
            ter = 0;
            for (int x:ind){
                dfs(x);
            }
            vector<kraw> kop = krawedzie[kol]; krawedzie[kol].clear();
            for (kraw x:kop){
                if (gdzie[x.nr] == 0){
                    krawedzie[kol].push_back(x);
                }
                else{
                    krawedzie[kol + (1<<k)].push_back(x);
                }
            }
        }
    }
    for (int x=0;x<(1<<K);x++){
        for (kraw y:krawedzie[x]){
            if (y.nr != -1) odp[y.nr] = x+1;
        }
    }
    cout << (1<<pot) << '\n';
    for (int x=0;x<m;x++) cout << odp[x] << '\n';
    return 0;
}

Compilation message

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<kraw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int x=0;x<krawedzie[kol].size();x++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11092 KB Output is correct
2 Correct 6 ms 11224 KB Output is correct
3 Correct 5 ms 11156 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 6 ms 11152 KB Output is correct
3 Correct 5 ms 11156 KB Output is correct
4 Correct 5 ms 11220 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12376 KB Output is correct
2 Correct 12 ms 12148 KB Output is correct
3 Correct 14 ms 12612 KB Output is correct
4 Correct 7 ms 11860 KB Output is correct
5 Correct 8 ms 11860 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12372 KB Output is correct
2 Correct 11 ms 12116 KB Output is correct
3 Correct 14 ms 12640 KB Output is correct
4 Correct 8 ms 11964 KB Output is correct
5 Correct 7 ms 11604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 73016 KB Output is correct
2 Correct 4309 ms 115700 KB Output is correct
3 Correct 1263 ms 103840 KB Output is correct
4 Correct 646 ms 81340 KB Output is correct
5 Correct 557 ms 60648 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 73084 KB Output is correct
2 Correct 1379 ms 98296 KB Output is correct
3 Correct 2371 ms 113664 KB Output is correct
4 Correct 639 ms 81372 KB Output is correct
5 Correct 145 ms 26664 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2691 ms 123056 KB Output is correct
2 Correct 3258 ms 109456 KB Output is correct
3 Correct 157 ms 26380 KB Output is correct
4 Correct 786 ms 79960 KB Output is correct
5 Correct 181 ms 51768 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 94256 KB Output is correct
2 Correct 5467 ms 116852 KB Output is correct
3 Correct 3483 ms 119192 KB Output is correct
4 Correct 982 ms 83780 KB Output is correct
5 Correct 622 ms 81392 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 87764 KB Output is correct
2 Correct 4963 ms 126764 KB Output is correct
3 Correct 3819 ms 121004 KB Output is correct
4 Correct 884 ms 83832 KB Output is correct
5 Correct 748 ms 81572 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 87828 KB Output is correct
2 Correct 4660 ms 127072 KB Output is correct
3 Correct 2881 ms 112156 KB Output is correct
4 Correct 176 ms 30376 KB Output is correct
5 Correct 762 ms 80624 KB Output is correct