Submission #535843

#	Time	Username	Problem	Language	Result	Execution time	Memory
535843		mario05092929	Swapping Cities (APIO20_swap)	C++17	100 / 100	311 ms	37916 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9+1;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,m,ans[100005],deg[100005];
vecpi p[100005];
vec ch[100005];
vector <pair<int,pi>> edge;

void init(int N,int M,vec U,vec V,vec W) {
    n = N, m = M;
    for(int i = 0;i < N;i++) {
        p[i].pb({0,i});
        ch[i].pb(i);
        ans[i] = INF;
    }
    for(int i = 0;i < M;i++) {
        edge.pb({W[i],{U[i],V[i]}});
    }
    sort(all(edge));
    for(auto I : edge) {
        int val = I.x, x = I.y.x, y = I.y.y;
        int px = p[x].back().y, py = p[y].back().y;
        if(px == py) {
            ans[px] = min(ans[px],val);
        }
        else {
            if(ch[px].size() < ch[py].size()) {
                swap(x,y), swap(px,py);
            }
            deg[x]++, deg[y]++;
            ans[px] = min(ans[px],max(ans[py],val));
            if(deg[x] > 2||deg[y] > 2) ans[px] = min(ans[px],val);
            for(int i : ch[py]) {
                p[i].pb({val,px});
                ch[px].pb(i);
            }
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    int i = p[x].size(), j = p[y].size();
    int ret = INF;
    i--, j--;
    while(i >= 0&&j >= 0&&p[x][i].y == p[y][j].y) {
        ret = min(ret,max({ans[p[x][i].y],p[x][i].x,p[y][j].x}));
        i--, j--;
    }
    return (ret == INF ? -1 : ret);
}

Compilation message (stderr)

swap.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("O3")
      | 
swap.cpp:8: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    8 | #pragma gcc optimize("Ofast")
      | 
swap.cpp:9: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    9 | #pragma gcc optimize("unroll-loops")
      |

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