oj.uz

Submission #334847

# Submission time Handle Problem Language Result Execution time Memory
334847 2020-12-10T05:34:24 Z limabeans Swapping Cities (APIO20_swap) C++17
0 / 100
 222 ms 36040 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]}});
    }


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

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

    for (auto ed: edges) {
	int w = ed.first;
	int u = ed.second.first;
	int v = ed.second.second;
	
	if (parent(u)==parent(v)) {
	    if (!good[indx[u]]) {
		g[head].push_back(indx[u]);
		good[head]=true;
		cost[head]=w;
		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;
	    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 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 Correct 17 ms 24044 KB Output is correct
5 Correct 17 ms 24300 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 18 ms 24172 KB Output is correct
8 Correct 17 ms 24300 KB Output is correct
9 Correct 64 ms 32352 KB Output is correct
10 Correct 76 ms 33760 KB Output is correct
11 Correct 74 ms 33632 KB Output is correct
12 Correct 77 ms 34144 KB Output is correct
13 Correct 76 ms 34144 KB Output is correct
14 Correct 71 ms 32480 KB Output is correct
15 Correct 141 ms 35712 KB Output is correct
16 Correct 151 ms 35448 KB Output is correct
17 Correct 144 ms 36040 KB Output is correct
18 Correct 150 ms 35932 KB Output is correct
19 Incorrect 78 ms 29356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 222 ms 35204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 24044 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 24044 KB Output isn't correct

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 Correct 17 ms 24044 KB Output is correct
5 Correct 17 ms 24300 KB Output is correct
6 Correct 17 ms 24172 KB Output is correct
7 Correct 18 ms 24172 KB Output is correct
8 Correct 17 ms 24300 KB Output is correct
9 Correct 64 ms 32352 KB Output is correct
10 Correct 76 ms 33760 KB Output is correct
11 Correct 74 ms 33632 KB Output is correct
12 Correct 77 ms 34144 KB Output is correct
13 Correct 76 ms 34144 KB Output is correct
14 Correct 71 ms 32480 KB Output is correct
15 Correct 141 ms 35712 KB Output is correct
16 Correct 151 ms 35448 KB Output is correct
17 Correct 144 ms 36040 KB Output is correct
18 Correct 150 ms 35932 KB Output is correct
19 Incorrect 222 ms 35204 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 24044 KB Output isn't correct