Submission #291652

#	Time	Username	Problem	Language	Result	Execution time	Memory
291652		shayan_p	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	592 ms	29936 KiB

railroad

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "railroad.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

int pr[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return 0;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
    return 1;
}


ll plan_roller_coaster(vector<int> a, vector<int> b){
    memset(pr, -1, sizeof pr);
    
    int n = sz(a);
    map<int, int> mp;
    mp[0]++; // first of all
    for(int x : a)
	mp[x]--;
    for(int x : b)
	mp[x]++;

    vector<int> tot;
    for(int x : a)
	tot.PB(x);
    for(int x : b)
	tot.PB(x);
    sort(tot.begin(), tot.end());
    tot.resize( unique(tot.begin(), tot.end()) - tot.begin() );

    auto comp = [&](int x){
		    return lower_bound(tot.begin(), tot.end(), x) - tot.begin() + 1;
		};
    int mrgs = 0;
    for(int i = 0; i < n; i++){
	mrgs+= mrg(comp(a[i]), comp(b[i]));
    }
    
    int sum = 0, ID = 0;
    for(auto it = mp.begin(); it != mp.end(); it++, ID++){
	sum+= it->S;
	if(sum < 0)
	    return 10;
	if(sum > 0)
	    mrgs+= mrg(ID, ID + 1);
    }
    if(mrgs != sz(tot) + 2 - 1)
	return 9;
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36