Submission #789666

#	Time	Username	Problem	Language	Result	Execution time	Memory
789666		Piokemon	Teoretičar (COCI18_teoreticar)	C++17	52 / 130	5359 ms	145936 KiB

teoreticar

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

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