Submission #313590

#	Time	Username	Problem	Language	Result	Execution time	Memory
313590		juggernaut	Swapping Cities (APIO20_swap)	C++14	100 / 100	746 ms	52840 KiB

swap

//#include"grader.cpp"
#include"swap.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
vector<pair<int,int>>g[100005];
vector<int>child[100005];
int timer,tin[100005],tout[100005],up[100005][17],sp1[100005][17],sp2[100005][17],inf=2e9,par[100005],deg[100005];
int fin(int v){
    if(v==par[v])return v;
    return par[v]=fin(par[v]);
}
void dfs(int v,int p,int cost){
    tin[v]=++timer;
    up[v][0]=p;
    sp1[v][0]=cost;
    for(int i=1;i<17;i++){
        up[v][i]=up[up[v][i-1]][i-1];
        sp1[v][i]=max(sp1[v][i-1],sp1[up[v][i-1]][i-1]);
        sp2[v][i]=min(sp2[v][i-1],sp2[up[v][i-1]][i-1]);
    }
    for(auto to:g[v])if(to.fr!=p)dfs(to.fr,v,to.sc);
    tout[v]=++timer;
}
bool upper(int a,int b){
    return tin[a]<tin[b]&&tout[a]>tout[b];
}
int lca(int a,int b){
	if(upper(a,b))return a;
	if(upper(b,a))return b;
	for(int i=16;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i];
	return up[a][0];
}
int fin1(int a,int p){
    int res=0;
    for(int i=16;i>=0;i--)
        if(!upper(up[a][i],p)){
            res=max(res,sp1[a][i]);
            a=up[a][i];
        }
    return res;
}
int fin2(int a,int p){
    int res=inf;
    for(int i=16;i>=0;i--)
        if(!upper(up[a][i],p)){
            res=min(res,sp2[a][i]);
            a=up[a][i];
        }
    return res;
}
bool cmp(pair<int,int>l,pair<int,int>r){
    return l.sc<r.sc;
}
void add_edge(int a,int b,int c){
    int aa=fin(a),bb=fin(b);
    deg[a]++;
    deg[b]++;
    if(aa!=bb){
        if( sp2[aa][0]==inf && ( sp2[bb][0]!=inf ||deg[a]==3||deg[b]==3 )){
            for(int i = 0; i<child[aa].size(); i++){
                sp2[child[aa][i]][0]=c;
            }
            child[aa].clear();
        }
        if( sp2[bb][0]==inf && ( sp2[aa][0]!=inf ||deg[a]==3||deg[b]==3 )){
            for(int i = 0; i<child[bb].size(); i++){
                sp2[child[bb][i]][0]=c;
            }
            child[bb].clear();
        }
        g[a].push_back({b,c});
        g[b].push_back({a,c});
        if(child[aa].size()<child[bb].size())swap(aa,bb);
        par[bb]=aa;
        child[aa].insert(child[aa].end(),child[bb].begin(),child[bb].end());
        child[bb].clear();
    }else{
        if(sp2[aa][0]==inf){
            for(int i = 0; i<child[aa].size(); i++){
                sp2[child[aa][i]][0]=c;
            }
            child[aa].clear();
        }
    }
}
bool cmp2(pair<pair<int,int>,int>l,pair<pair<int,int>,int>r){
    return l.sc<r.sc;
}
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W){
    for(int i=0;i<N;i++)child[i].push_back(i),par[i]=i,sp2[i][0]=inf;
    vector<pair<pair<int,int>,int>>ed;
    for(int i=0;i<M;i++)ed.push_back({{U[i],V[i]},W[i]});
    sort(ed.begin(),ed.end(),cmp2);
    for(auto to:ed)
        add_edge(to.fr.fr,to.fr.sc,to.sc);
    for(int i=0;i<N;i++)sort(g[i].begin(),g[i].end(),cmp);
    dfs(0,0,0);
}
int getMinimumFuelCapacity(int X,int Y){
    int l=lca(X,Y),res;
    res=max(min(fin2(X,l),fin2(Y,l)),max(fin1(X,l),fin1(Y,l)));
    if(res==inf)res=-1;
    return res;
}

Compilation message (stderr)

swap.cpp: In function 'void add_edge(int, int, int)':
swap.cpp:62:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int i = 0; i<child[aa].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~
swap.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i = 0; i<child[bb].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~
swap.cpp:81:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int i = 0; i<child[aa].size(); i++){
      |                            ~^~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27