Submission #1264511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264511		gotkako	World Map (IOI25_worldmap)	C++20	100 / 100	208 ms	3648 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;

bool test = false;
void output(vector<vector<int>> A){
    for(auto a : A){
        for(auto aa : a) cout << aa+1 << " ";
        cout << endl;
    }
        cout << endl;
}

vector<int> BFS(vector<vector<int>> Graph,int start){
    int N = Graph.size();
    vector<int> ret(N,-1);
    queue<int> Q; Q.push(start);
    ret.at(start) = 0;
    while(Q.size()){
        int pos = Q.front(); Q.pop();
        for(auto to : Graph.at(pos)) if(ret.at(to) == -1){
            ret.at(to) = ret.at(pos)+1;
            Q.push(to);
        }
    }
    return ret;
}

vector<pair<char,long long>> RLE(string &s){
    if(s.size() == 0) return {};
    vector<pair<char,long long>> ret;
    char back = s.at(0);
    long long streak = 1;
    for(int i=1; i<s.size(); i++){
        if(back == s.at(i)) streak++;
        else{
            ret.push_back({back,streak});
            back = s.at(i); streak = 1;
        }
    }
    ret.push_back({back,streak});
    return ret;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    for(auto &a : A) a--;
    for(auto &b : B) b--;
    vector<vector<int>> Graph(N),Tree(N);
    for(int i=0; i<M; i++){
        int a = i,b = i+1;
        a = A.at(i),b = B.at(i);
        Graph.at(a).push_back(b);
        Graph.at(b).push_back(a);
    }
    int start = -1;
    vector<int> H(N);
    {
        vector<bool> ok(N);
        for(int i=0; i<N; i++) if(Graph.at(i).size()){
            auto f = [&](auto f,int pos) -> void {
                ok.at(pos) = true;
                for(auto to : Graph.at(pos)) if(!ok.at(to)){
                    Tree.at(pos).push_back(to);
                    Tree.at(to).push_back(pos);
                    f(f,to);
                }
            };
            f(f,i);
            int D = -1;
            for(int p=0; p<N; p++){
                auto dist = BFS(Tree,p);
                int maxd = *max_element(dist.begin(),dist.end());
                if(D < maxd) D = maxd,start = p; 
            }
            auto g = [&](auto g,int pos,int back) -> int {
                int ret = 0;
                for(auto to : Tree.at(pos)) if(to != back) ret = max(ret,g(g,to,pos));
                H.at(pos) = ret;
                return ret;
            };
            g(g,start,-1);
            break;
        }
    }

    int K = 240;
    int X = 0;
    vector<vector<int>> C(K,vector<int>(K,-1));
    C.at(0).assign(K,0);
    vector<vector<bool>> paint(N,vector<bool>(N)),edge = paint;
    for(int i=0; i<M; i++) edge.at(A.at(i)).at(B.at(i)) = true,edge.at(B.at(i)).at(A.at(i)) = true;


    vector<bool> already(N);
    vector<vector<vector<int>>> Lens(K,vector<vector<int>>(K));
    auto dfs = [&](auto dfs,int pos,int back) -> void {
        X++;
        already.at(pos) = true;
        int Y = 0,n = (int)Graph.at(pos).size(),left = n;
        vector<bool> posok(n);
        for(int i=0; i<n; i++){
            int to = Graph.at(pos).at(i);
            if(paint.at(pos).at(to)) posok.at(i) = true,left--;
        }
        for(int i=0; i<n; i++) if(!posok.at(i)){
            bool alone = true;
            int to = Graph.at(pos).at(i);
            for(int k=0; k<n; k++) if(!posok.at(k) && edge.at(to).at(Graph.at(pos).at(k))){
                alone = false; break;
            }
            if(alone){
                paint.at(to).at(pos) = true;
                paint.at(pos).at(to) = true;
                posok.at(i) = true;
                C.at(X).at(Y++) = to,C.at(X).at(Y++) = pos;
                Lens.at(X).at(1).push_back(Y-2); break;
            }
        }
        if(left && Y == 0) C.at(X).at(Y++) = pos;
        for(int i=0; i<n; i++) if(posok.at(i) == false){
            posok.at(i) = true;
            int to = Graph.at(pos).at(i);
            C.at(X).at(Y++) = to;
            paint.at(pos).at(to) = true;
            paint.at(to).at(pos) = true;
            int len = 1;
            for(int k=i+1; k<n; k++) if(!posok.at(k) && edge.at(to).at(Graph.at(pos).at(k))){
                int to2 = Graph.at(pos).at(k);
                C.at(X).at(Y++) = to2;
                paint.at(pos).at(to2) = true;
                paint.at(to2).at(pos) = true;
                paint.at(to).at(to2) = true;
                paint.at(to2).at(to) = true;
                posok.at(k) = true,len = 2; break;
            }
            Lens.at(X).at(len).push_back(Y-len);
            C.at(X).at(Y++) = pos;
        }
        for(int i=0; i<n&&Y>0&&Y+2<=2*N; i++) for(int k=i+1; k<n&&Y+2<=2*N; k++){
            int to1 = Graph.at(pos).at(i),to2 = Graph.at(pos).at(k);
            if(paint.at(to1).at(to2) || !edge.at(to1).at(to2)) continue;
            paint.at(to1).at(to2) = true;
            paint.at(to2).at(to1) = true;
            C.at(X).at(Y++) = to1;
            C.at(X).at(Y++) = to2;
            int len = 2;
            while(Y < 2*N){
                bool change = false;
                for(int l=0; l<n; l++){
                    int to3 = Graph.at(pos).at(l);
                    if(paint.at(to2).at(to3) || !edge.at(to2).at(to3)) continue;
                    paint.at(to2).at(to3) = true;
                    paint.at(to3).at(to2) = true;
                    C.at(X).at(Y++) = to3;
                    change = true,to2 = to3; break;
                }
                if(!change) break;
                len++;
            }
            Lens.at(X).at(len).push_back(Y-len);
            if(Y < 2*N) C.at(X).at(Y++) = pos;
        }
    
        if(Y != 0){
            for(; Y<2*N; Y++) C.at(X).at(Y) = pos;
            C.at(++X).assign(K,pos);
        }    
        sort(Tree.at(pos).begin(),Tree.at(pos).end(),[&](auto a,auto b){return H.at(a)<H.at(b);});
        for(auto to : Tree.at(pos)){
            if(to == back) continue;
            X++;
            for(int i=0; i<K; i++) C.at(X).at(i) = to;
            dfs(dfs,to,pos);
            for(int i=0; i<K; i++) C.at(X).at(i) = pos;
        }
        X++;
    };
    if(start != -1){
        C.at(0).assign(K,start);
        dfs(dfs,start,-1);
    }    
    K = max(2*N,X);
    C.resize(K),Lens.resize(K);
    if(K > 2*N) C.erase(C.begin()),K--,Lens.erase(Lens.begin());
    for(int i=0; i<K; i++){
        C.at(i).resize(K);
        if(C.at(i).at(0) == -1) C.at(i).at(0) = C.at(i-1).at(0);
        for(int k=1; k<K; k++) if(C.at(i).at(k) == -1) C.at(i).at(k) = C.at(i).at(k-1);
    }
    while(K > 2*N){
        set<int> now(C.back().begin(),C.back().end());
        if(now.size() == 1) C.pop_back(),K--,Lens.pop_back();
        else break;
    }
    while(K > 2*N){
        bool change = false;
        while(K > 2*N){
            vector<int> same(K,-1);
            for(int i=0; i<K; i++){
                for(auto c : C.at(i)){
                    if(same.at(i) == -1) same.at(i) = c;
                    else if(same.at(i) != c) same.at(i) = -2;
                }
            }
            bool end = true;
            for(int i=0; i<K&&end; i++){
                if(same.at(i) == -2) continue;
                int r = i;
                while(r < K && same.at(r) != -2) r++;
                int len = r-i;
                for(int k=len-1; k>0; k--){
                    for(int l=i; l+k<r; l++){
                        int p1 = same.at(l),p2 = same.at(l+k);
                        if(p1 == p2){
                            end = false;
                            for(int p=l+k; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
                            break;
                        }
                        else if(paint.at(p1).at(p2) && k > 1){
                            end = false;
                            for(int p=l+k-1; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
                            break;
                        }
                    }
                    if(end == false) break;
                }
            }
            if(end) break;
            change = true;
        }
        while(K > 2*N){
            vector<int> same(K,-1);
            for(int i=0; i<K; i++){
                for(int k=0; k<C.at(i).size(); k++){
                    if(k == 0) same.at(i) = C.at(i).at(k);
                    else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
                }
            }
            
            for(int i=0; i<K-2; i++){
                int s3 = same.at(i+1);
                if(s3 == -2) continue;
                int s4 = same.at(i+2);
                if(s4 == -2) continue;
                bool del = true;
                for(auto c : C.at(i)) if(edge.at(c).at(s4) == false && c != s4){del = false; break;}
                if(del == false) continue;
                C.erase(C.begin()+i+1),Lens.erase(Lens.begin()+i+1);
                break;
            }
            if(C.size() == K){
                for(int i=0; i<K-1; i++) if(same.at(i) != -2 && same.at(i) == same.at(i+1)){
                    C.erase(C.begin()+i),Lens.erase(Lens.begin()+i); break;
                }
            }
            if(C.size() == K) break;
            K--; change = true;
        }
        if(change) continue;

        while(K > 2*N){
            vector<int> same(K,-1);
            for(int i=0; i<K; i++){
                for(int k=0; k<C.at(i).size(); k++){
                    if(k == 0) same.at(i) = C.at(i).at(k);
                    else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
                }
            }
            bool end = true;
            for(X=3; X<K; X++){
                if(same.at(X-2) == -2 || same.at(X-1) == -2) continue;
                auto Len = Lens.at(X);
                bool zero = true;
                for(auto l : Len) if(l.size()){zero = false; break;}
                if(zero) continue;
                
                string s(2*N,'x');
                for(int i=1; i<2*N-1; i++) if(C.at(X-3).at(i) == C.at(X-2).at(i)) s.at(i) = 'o';
                
                //cout << X+1 << " " << s << endl;
                //for(int i=0; i<2*N; i++) cout << C.at(X-3).at(i) << " "; cout << endl;
                //for(int i=0; i<2*N; i++) cout << C.at(X-2).at(i) << " "; cout << endl;
                //for(int i=0; i<2*N; i++) cout << C.at(X-1).at(i) << " "; cout << endl;
                //for(int i=0; i<2*N; i++) cout << C.at(X).at(i) << " "; cout << endl;
                
                auto S = RLE(s);
                int leader = C.at(X-1).at(0);
                vector<int> move(K,leader);
                vector<pair<int,int>> space;
                int p = 0;
                for(auto [c,len] : S){
                    if(c == 'o') space.push_back({len,p});
                    p += len;
                }
                sort(space.begin(),space.end());
                int l = 1;
                for(auto [len,p] : space){
                    while(len >= l && l < K){
                        if(Len.at(l).size() == 0){l++; continue;}
                        int s = Len.at(l).back(); Len.at(l).pop_back();
                        for(int q=s; q<s+l; q++) move.at(p++) = C.at(X).at(q);
                        len -= l;
                        if(len) len--,p++;
                    }
                    while(l < K && Len.at(l).size() == 0) l++;
                    if(l == K) break;
                }
                if(l == K){
                    end = false;
                    for(int i=0; i<2*N; i++){
                        if(move.at(i) != leader) C.at(X-1).at(i) = move.at(i),C.at(X-2).at(i) = leader;
                    }
                    C.erase(C.begin()+X),Lens.erase(Lens.begin()+X);
                    break;
                }    
            }
            if(end) break;
            change = true;
            K--; break;
        }
        if(change == false) break;
    }
    if(K > 2*N) for(auto &c : C) c.resize(2*N);

    while(K > 2*N){
        bool change = false;
        while(K > 2*N && false){
            vector<int> same(K,-1);
            for(int i=0; i<K; i++){
                for(auto c : C.at(i)){
                    if(same.at(i) == -1) same.at(i) = c;
                    else if(same.at(i) != c) same.at(i) = -2;
                }
            }
            bool end = true;
            for(int i=0; i<K&&end; i++){
                if(same.at(i) == -2) continue;
                int r = i;
                while(r < K && same.at(r) != -2) r++;
                int len = r-i;
                for(int k=len-1; k>0; k--){
                    for(int l=i; l+k<r; l++){
                        int p1 = same.at(l),p2 = same.at(l+k);
                        if(p1 == p2){
                            end = false;
                            for(int p=l+k; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
                            break;
                        }
                        else if(paint.at(p1).at(p2) && k > 1){
                            end = false;
                            for(int p=l+k-1; p>l; p--) C.erase(C.begin()+p),K--,Lens.erase(Lens.begin()+p);
                            break;
                        }
                    }
                    if(end == false) break;
                }
            }
            if(end) break;
            change = true;
        }
        while(K > 2*N){
            vector<int> same(K,-1);
            for(int i=0; i<K; i++){
                for(int k=0; k<C.at(i).size(); k++){
                    if(k == 0) same.at(i) = C.at(i).at(k);
                    else if(same.at(i) != C.at(i).at(k)){same.at(i) = -2; break;}
                }
            }
            
            for(int i=0; i<K-2; i++){
                int s3 = same.at(i+1);
                if(s3 == -2) continue;
                int s4 = same.at(i+2);
                if(s4 == -2) continue;
                bool del = true;
                for(auto c : C.at(i)) if(edge.at(c).at(s4) == false && c != s4){del = false; break;}
                if(del == false) continue;
                C.erase(C.begin()+i+1),Lens.erase(Lens.begin()+i+1);
                break;
            }
            if(C.size() == K){
                for(int i=0; i<K-1; i++) if(same.at(i) != -2 && same.at(i) == same.at(i+1)){
                    C.erase(C.begin()+i),Lens.erase(Lens.begin()+i); break;
                }
            }
            if(C.size() == K) break;
            K--; change = true;
        }
        if(change) continue;

        //output(C);
        for(int i=K-1; i>=0; i--){
            if(i) for(int k=0; k<2*N; k++){
                int c = C.at(i).at(k),c2 = c,c3 = c,c4 = c;
                if(k) c2 = C.at(i).at(k-1);
                if(k < 2*N-1) c3 = C.at(i).at(k+1);
                if(i+1 < K) c4 = C.at(i+1).at(k);
                if(c == c2 && c2 == c3 && c3 == c4){
                    int d = C.at(i-1).at(k),d2 = d,d3 = d,d4 = d;
                    if(k) d2 = C.at(i-1).at(k-1);
                    if(k < 2*N-1) d3 = C.at(i-1).at(k+1);
                    if(i-1) d4 = C.at(i-2).at(k);
                    if(d == d2 && d2 == d3 && d3 == d4)  C.at(i-1).at(k) = c; 
                }
            }
            if(i) for(int k=2*N-1; k>=0; k--){
                int c = C.at(i).at(k),c2 = c,c3 = c,c4 = c;
                if(k) c2 = C.at(i).at(k-1);
                if(k < 2*N-1) c3 = C.at(i).at(k+1);
                if(i+1 < K) c4 = C.at(i+1).at(k);
                if(c == c2 && c2 == c3 && c3 == c4){
                    int d = C.at(i-1).at(k),d2 = d,d3 = d,d4 = d;
                    if(k) d2 = C.at(i-1).at(k-1);
                    if(k < 2*N-1) d3 = C.at(i-1).at(k+1);
                    if(i-1) d4 = C.at(i-2).at(k);
                    if(d == d2 && d2 == d3 && d3 == d4)  C.at(i-1).at(k) = c; 
                }
            }
            if(i < K-1) for(int k=0; k<2*N; k++){
                int c = C.at(i+1).at(k),d = C.at(i).at(k);
                if(c == d) continue;
                int d2 = c,d3 = c,d4 = d;
                if(k) d2 = C.at(i).at(k-1);
                if(k < 2*N-1) d3 = C.at(i).at(k+1);
                if(i) d4 = C.at(i-1).at(k);
                if(d != d4) continue;
                if(d2 == c || d2 == d){
                    if(d3 == c || d3 == d){
                        if(i || d2 == d || d3 == d) C.at(i).at(k) = C.at(i+1).at(k); 
                    }
                }
            }
            if(i < K-1) for(int k=2*N-1; k>=0; k--){
                int c = C.at(i+1).at(k),d = C.at(i).at(k);
                if(c == d) continue;
                int d2 = c,d3 = c,d4 = d;
                if(k) d2 = C.at(i).at(k-1);
                if(k < 2*N-1) d3 = C.at(i).at(k+1);
                if(i) d4 = C.at(i-1).at(k);
                if(d != d4) continue;
                if(d2 == c || d2 == d){
                    if(d3 == c || d3 == d){
                        if(i || d2 == d || d3 == d) C.at(i).at(k) = C.at(i+1).at(k); 
                    }
                }
            }
        }

        vector<vector<int>> near(N,vector<int>(N));
        for(int i=0; i<K; i++) for(int k=0; k<2*N; k++){
            if(i+1 < K){
                int c = C.at(i).at(k);
                int c2 = C.at(i+1).at(k);
                near.at(c).at(c2)++;
                near.at(c2).at(c)++;
            }
            if(k+1 < 2*N){
                int c = C.at(i).at(k);
                int c2 = C.at(i).at(k+1);
                near.at(c).at(c2)++;
                near.at(c2).at(c)++;
            }
        }
        for(int i=K-1; i>=0; i--) for(int k=2*N; k--;){
            int c = C.at(i).at(k),c2 = -1,c3 = -1,c4 = -1,c5 = -1;
            int ne = 0;
            if(i) c2 = C.at(i-1).at(k),ne++;
            if(k) c3 = C.at(i).at(k-1),ne++;
            if(k < 2*N-1) c4 = C.at(i).at(k+1),ne++;
            if(i+1 < K) c5 = C.at(i+1).at(k),ne++;
            if(c3 == -1) c3 = c2;
            if(c4 == -1) c4 = c3;
            if(c5 == -1) c5 = c4;
            if(c4 == -1) c4 = c5;
            if(c3 == -1) c3 = c4;
            if(c2 == -1) c2 = c3;
            if(c2 == c3 && c3 == c4 && c4 == c5 && c != c2 && near.at(c).at(c2) > ne){
                C.at(i).at(k) = c2; near.at(c).at(c2) -= ne,near.at(c2).at(c) -= ne;
                break;
            }  
        }
        //output(C);
        for(int i=K-1; i>0&&K>2*N; i--) if(C.at(i) == C.at(i-1)){C.erase(C.begin()+i),K--;}
        //output(C);
    }

    K = max(2*N,K); Lens.clear();
    while(C.size() < K) C.push_back(vector<int>(K,-1));
    for(int i=0; i<K; i++){
        C.at(i).resize(K);
        if(C.at(i).at(0) == -1){
            for(int k=0; k<N; k++){
                bool ok = true;
                for(auto c : C.at(i-1)) if(edge.at(c-1).at(k) == false && c-1 != k){ok = false; break;}
                if(ok){C.at(i).at(0) = k; break;}
            }
        }    
        for(int k=1; k<K; k++) if(C.at(i).at(k) == -1) C.at(i).at(k) = C.at(i).at(k-1);
        for(auto &c : C.at(i)) c++;
    }
    for(auto &c : C) while(c.size() > K) c.pop_back();
    set<pair<int,int>> UV,AB;
    for(int i=0; i<M; i++) AB.insert({min(A.at(i),B.at(i)),max(A.at(i),B.at(i))});
    for(int i=0; i<K; i++) for(int k=0; k<K; k++){
        int c = C.at(i).at(k);
        if(k+1 < K){
            int c2 = C.at(i).at(k+1);
            UV.insert({min(c,c2)-1,max(c,c2)-1});
        }
        if(i+1 < K){
            int c2 = C.at(i+1).at(k);
            UV.insert({min(c,c2)-1,max(c,c2)-1});
        }
    }
    for(int i=0; i<N; i++) if(UV.count({i,i})) UV.erase({i,i}); 
    if(AB != UV){
        cout << "You" << endl;
        for(auto [u,v] : UV) cout << u+1 << " " << v+1 << endl;
        cout << "AB" << endl;
        for(auto [u,v] : AB) cout << u+1 << " " << v+1 << endl;
    }
    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 56 / 56