oj.uz

Submission #334857

# Submission time Handle Problem Language Result Execution time Memory
334857 2020-12-10T05:44:19 Z limabeans Swapping Cities (APIO20_swap) C++17
7 / 100
 438 ms 59592 KB 
#include <bits/stdc++.h>
#include "swap.h"

using namespace std;


const int maxn = 1e6 + 10;

int n, m;
vector<int> g[maxn];
vector<pair<int,pair<int,int>>> edges;
int head;

int par[maxn];
int indx[maxn];
int deg[maxn];
bool good[maxn];
int cost[maxn];

int parent(int x) {
    if (par[x]==x) return x;
    return par[x]=parent(par[x]);
}

const int LOG = 20;
int st[LOG+1][maxn];
int ht[maxn];

void dfs(int at, int p=-1) {
    for (int j=1; j<LOG; j++) {
	st[j][at]=st[j-1][st[j-1][at]];
    }
    for (int to: g[at]) {
	if (to == p) continue;
	st[0][to]=at;
	ht[to] = 1+ht[at];
	dfs(to, at);
    }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;
    m=M;
    head = n;
    for (int i=0; i<M; i++) {
	edges.push_back({W[i],{U[i],V[i]}});
    }

    sort(edges.begin(),edges.end());


    for (int i=0; i<n; i++) {
	par[i]=i;
	indx[i]=i;
	deg[i]=0;
	good[i]=false;
    }



    for (auto ed: edges) {
	int w = ed.first;
	int U = ed.second.first;
	int V = ed.second.second;
	int u = parent(U);
	int v = parent(V);
	
	if (u==v) {
	    if (!good[indx[u]]) {
		g[head].push_back(indx[u]);
		good[head]=true;
		cost[head]=w;
		indx[u] = head++;
	    }
	} else {
	    deg[u]++;
	    deg[v]++;
	    
	    bool ok = (good[indx[u]] || good[indx[v]] || deg[U]>2 || deg[V]>2);
	    par[v]=u;
	    g[head].push_back(indx[u]);
	    g[head].push_back(indx[v]);
	    good[head] = ok;
	    cost[head] = w;
	    indx[u] = head++;
	}
    }

    st[0][head-1] = head-1;
    dfs(head-1);
}

int lca(int u, int v) {
    if (ht[u]<ht[v]) {
	swap(u,v);
    }
    int dx = ht[u]-ht[v];
    for (int j=LOG-1; j>=0; j--) {
	if (dx>>j&1) {
	    u=st[j][u];
	}
    }
    if (u==v) return v;
    
    for (int j=LOG-1; j>=0; j--) {
	if (st[j][u]!=st[j][v]) {
	    u=st[j][u];
	    v=st[j][v];
	}
    }
    
    return st[0][v];
}

int getMinimumFuelCapacity(int u, int v) {
    if (!good[head-1]) return -1;

    int mid = lca(u,v);
    if (good[mid]) {
	return cost[mid];
    }

    for (int j=LOG-1; j>=0; j--) {
	if (ht[mid] < (1<<j)) continue;
	if (!good[st[j][mid]]) {
	    mid=st[j][mid];
	}
    }

    return cost[st[0][mid]];
}

/*
int main() {
    // init(4,4,{0,1,2,3},{1,2,3,0},{1,1,1,1});
    // cout<<getMinimumFuelCapacity(1, 2)<<endl;

    
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout<<getMinimumFuelCapacity(1, 2)<<endl;
    cout<<getMinimumFuelCapacity(2, 4)<<endl;
    cout<<getMinimumFuelCapacity(0, 1)<<endl;
    
    return 0;
}
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Incorrect 17 ms 24172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 405 ms 57988 KB Output is correct
4 Correct 410 ms 59592 KB Output is correct
5 Correct 424 ms 58616 KB Output is correct
6 Correct 406 ms 59336 KB Output is correct
7 Correct 438 ms 59232 KB Output is correct
8 Correct 412 ms 57872 KB Output is correct
9 Correct 410 ms 58848 KB Output is correct
10 Correct 408 ms 57696 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 17 ms 24044 KB Output is correct
5 Incorrect 17 ms 24172 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 17 ms 24044 KB Output is correct
5 Incorrect 17 ms 24172 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 16 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Incorrect 17 ms 24172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24044 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 16 ms 24044 KB Output is correct
4 Correct 17 ms 24044 KB Output is correct
5 Incorrect 17 ms 24172 KB Output isn't correct
6 Halted 0 ms 0 KB -