Submission #1126995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126995		HuyAT	Rope (JOI17_rope)	C++17	0 / 100	606 ms	327680 KiB

rope

#include<bits/stdc++.h>
#define newl '\n'

const int N = 3e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct DSU{
    std::vector<int> lab;
    DSU(){

    }
    DSU(int n) : lab(n + 1,-1){

    }
    int find_set(int i){
        return (lab[i] < 0 ? i : lab[i] = find_set(lab[i]));
    }
    bool same_set(int i,int j){
        return (find_set(i) == find_set(j));
    }
    void merg(int x,int y){
        x = find_set(x);
        y = find_set(y);
        if(x == y){
            return;
        }
//        if(-lab[x] > -lab[y]){
//            std::swap(x,y);
//        }
        lab[y] += lab[x];
        lab[x] = y;
    }
};
struct Tree{
    std::vector<std::vector<std::pair<int,int>>> adj;
    std::vector<int> par,in,out,id;
    DSU graph;
    void euler_tour(int u = 1){
        static int timer = 0;
        in[u] = ++timer;
        for(std::pair<int,int> nxt : adj[u]){
            int v = nxt.first;
            int curid = nxt.second;
            if(v == par[u]){
                continue;
            }
            par[v] = u;
            id[v] = curid;
            euler_tour(v);
        }
        out[u] = timer;
    }
//    void binlift(){
//        par[1][0] = 1;
//        for(int j = 1;j <= B;++j){
//            for(int i = 1;i <= n;++i){
//                par[i][j] = par[par[i][j - 1]][j - 1];
//            }
//        }
//    }
    bool isancestor(int u,int v){
        return (in[u] <= in[v] && out[u] >= out[v]);
    }
//    int lca(int u,int v){
//        if(isancestor(u,v)){
//            return u;
//        }
//        if(isancestor(v,u)){
//            return v;
//        }
//        for(int i = B;i >= 0;--i){
//            if(!isancestor(par,v)){
//
//            }
//        }
//    }
    void connect(int u,int v,std::vector<int> &eid){
        while(!isancestor(graph.find_set(u),v)){
            u = graph.find_set(u);
            eid.emplace_back(id[u]);
            graph.merg(u,par[u]);
        }
        while(!isancestor(graph.find_set(v),u)){
            v = graph.find_set(v);
            eid.emplace_back(id[v]);
            graph.merg(v,par[v]);
        }
    }
    Tree(std::vector<std::vector<std::pair<int,int>>> adj,int n) : adj(adj),par(n + 1),in(n + 1,0),out(n + 1,0),id(n + 1,0),graph(n + 1){
        euler_tour();
    }

};
bool keep[N + 1];
std::vector<int> adj[N + 1];
std::map<int,int> id[N + 1];
std::pair<int,int> e[N + 1];

int n,m,pans[N + 1];

void readData(){
    std::cin >> n >> m;
    for(int i = 1;i <= m;++i){
        int u,v;
        std::cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        e[i] = {u,v};
        if(u > v){
            std::swap(u,v);
        }
        id[u][v] = i;
    }
    for(int i = 1;i < n;++i){
        int it;
        std::cin >> it;
        keep[it] = true;
    }
}
namespace subtask1{
    void solve(){
        std::vector<int> ans;
        std::vector<int> perm(m,0);
        std::iota(perm.begin(),perm.end(),1);
//        perm = {3,4,5,1,2};
        do{
            std::vector<int> pos(m);
            bool valid = true;
            DSU graph(n);
            for(int i = 0;i < (int)perm.size();++i){
                pos[perm[i] - 1] = i;
            }
            for(int i = 0;i < m;++i){
                int it = pos[i];
                if(graph.same_set(e[it + 1].first,e[it + 1].second) && keep[it + 1]){
                    valid = false;
                }
                graph.merg(e[it + 1].first,e[it + 1].second);
//                std::cout << e[it + 1].first << " " << e[it + 1].second << newl;
            }
            if(valid){
                ans = perm;
                break;
            }
        }while(std::next_permutation(perm.begin(),perm.end()));
        for(int val : ans){
            std::cout << val << " ";
        }
    }
}
void solve(){
    std::vector<std::vector<std::pair<int,int>>> treeadj(n + 1);
    for(int i = 1;i <= m;++i){
        if(keep[i]){
            treeadj[e[i].first].emplace_back(e[i].second,i);
            treeadj[e[i].second].emplace_back(e[i].first,i);
        }
    }
    Tree tree(treeadj,n);
    int cnt = 0;
    for(int i = 1;i <= m;++i){
        if(!keep[i]){
            std::vector<int> eid;
            tree.connect(e[i].first,e[i].second,eid);
            std::sort(eid.begin(),eid.end());
            for(int it : eid){
                pans[it] = ++cnt;
            }
            pans[i] = ++cnt;
        }else{
            if(pans[i] == 0){
                std::vector<int> eid;
                tree.connect(e[i].first,e[i].second,eid);
                pans[i] = ++cnt;
            }
        }
    }
    for(int i = 1;i <= m;++i){
        std::cout << pans[i] << " ";
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
//    freopen("Palace.inp","r",stdin);
//    freopen("Palace.out","w",stdout);
    readData();
//    subtask1::solve();
    solve();
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20