Λύσεις Β φάσης 29ου ΠΔΠ

[infinity]

Εδώ μπορείτε να αναρτήσετε και να συζητήσετε τις λύσεις σας για τα προβλήματα της Β φάσης.

Καλή επιτυχία και καλή συνέχεια σε όλους

[Sinnosuke]

Αλγόριθμος Prim με priority_queue
Πολυπλοκότητα O(nlogn)

Κώδικας: Επιλογή όλων

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;

class Graph{
	int V;
public:
	vector<vector<pair<int,int> > > adj;
	Graph(int a);
	void addEdge(int u, int v, int w);
};

Graph::Graph (int a){
	V=a;
	adj.resize(V);
}

void Graph::addEdge(int u ,int v ,int w){
	adj[u].push_back(make_pair(v,w));
	adj[v].push_back(make_pair(u,w));
}

int main() {
	ifstream fin ;
	ofstream fout;
	fin.open("uflights.in");
	fout.open("uflights.out");

	int n,m;

	fin>> n >> m;

	Graph g(n);

	for(int ii=0;ii<m;ii++){
		int u,v,w;
		fin>>u>>v>>w;
		u--;
		v--;
		g.addEdge(u,v,w);
	}

	priority_queue< pair<int,int>, vector <pair<int,int> > , greater<pair<int , int > > > priority_q;
	vector<int> dist (n,INT_MAX);
	vector<bool> used (n,false);
	priority_q.push(make_pair(0,0));
	dist[0]=0;

	long long int answer=0;
	while(priority_q.empty()==false){
		int u=priority_q.top().second;
		if(used[u]==false)answer+=priority_q.top().first;
		priority_q.pop();
		used[u]=true;
		for(int ii=0;ii<g.adj[u].size();ii++){
			int v=g.adj[u][ii].first;
			int w=g.adj[u][ii].second;
			if(used[v]==false && dist[v]>w){
				dist[v]=w;
				priority_q.push(make_pair(w,v));
			}
		}
	}

	fout << answer << endl;

	return 0;
}

[qsort]

Κώδικας: Επιλογή όλων

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>

#define p2Int pair<int,int>
#define pIntP2Int pair<int,p2Int>
#define Nmax 1000001

using namespace std;

int edges , N ;
bool counter[Nmax] = {false};
typedef struct node {
	int x , y ;
	int weight ;
}node;
list<node> p ;

bool lessthan(const node& a,const node& b){
	return a.weight < b.weight ;
}

int mst(void){
	int minc = 0;
	while(!p.empty()){
		for(list<node>::iterator i = p.begin() ; i !=p.end() ; i++){
			if(counter[i->x] && counter[i->y]){
				p.erase(i);
				break ;
			}else if(!counter[i->x] && !counter[i->y]){
				continue ;
			}else{
				counter[i->x] = counter[i->y] = true ;
				minc += i->weight ;
				p.erase(i);
				break;
			}
		}
	}
	return minc ;
}

int main()
{
	printf("edges: ");
	scanf("%d",&edges);
	printf("nodes: ");
	scanf("%d",&N);
	int x,y,weight ;
	printf("write me the nodes syntax : ( weight(cost) , node a , node b )-:\n");
	for(int i = 0 ; i < N ; i++){
		scanf("%d %d %d",&x,&y,&weight);
		node temp ;
		temp.weight = weight ;
		temp.x = x ;
		temp.y = y ;
		p.push_back(temp);
	}

	p.sort(lessthan);
	printf("minimum cost is : %d\n",mst());
	return 0 ;
}

[qsort]

για το γυμνάσιο:

Κώδικας: Επιλογή όλων

#include <cstdio>
int 	N,K,A[1000001]={0},
	C[100001]={0},minC=2000000;
using namespace std;

int main(){
	FILE *in=fopen("colors.in","r"),*out=fopen("colors.out","w");
	fscanf(in,"%d%d",&N,&K);
	for(int R=1,L=1,nC=0;R<=N;R++){
		fscanf(in,"%d",A+R);
		if(C[A[R]]==0)
			nC++;
		C[A[R]] = R;
		if(nC == K){//are we colorful?
			while(L<R && C[A[L]]>L)
				L++;
			if(R-L+1 < minC)
				minC = R-L+1;
		}
	}
	fprintf(out,"%d\n",minC<=N?minC:0);
	return 0;
}

[giorgosgiapis]

Για το Λύκειο (αλγοριθμος Kruskal):

Κώδικας: Επιλογή όλων

#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

//#define LOCAL
#ifdef LOCAL
	#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
	#define DEBUG(x) 
#endif

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

inline int read(){  
	register int c = getc_unlocked(stdin);  
	int x = 0;  
	for(; (c < 48 || c > 57); c = getc_unlocked(stdin));  
	for(; (c > 47 && c < 58); c = getc_unlocked(stdin)){ x = (x << 1) + (x << 3) + c - 48; } 
	return x;
}  

struct Edge{
	int from, to;
	int weight;
	Edge(int from, int to, int weight)
		: from(from), to(to), weight(weight) {}
};

bool cmp(const Edge& a, const Edge& b){
	return a.weight < b.weight;
}

int id[100005], Rank[100005];

void Init(int n){
	for(int i = 0; i < n; i++){
		id[i] = i;
		Rank[i] = 0;
	}
}

int Find(int u){
	while(u != id[u]){
		id[u] = id[id[u]];
		u = id[u];
	}
	return u;
}

void Union(int u, int v){	
	int i = Find(u), j = Find(v);
	if(Rank[i] < Rank[j]) id[i] = j;
	else if(Rank[i] > Rank[j]) id[j] = i;
	else{
		id[i] = j;
		Rank[j]++;
	}
}

vector<Edge> edges;

int main(){

	freopen("uflights.in", "r", stdin);
	freopen("uflights.out", "w", stdout);

	int n = read();
	int m = read();

	int a, b, w;
	for(int i = 0; i < m; i++){
		a = read(), b = read(), w = read();
		a--, b--;	
		edges.pb(Edge(a, b, w));
	}

	sort(all(edges), cmp);

	Init(n);

	int ans = 0;
	for(int i = 0; i < edges.sz(); i++){
		int u = edges[i].from, v = edges[i].to;
		if(Find(u) != Find(v)){
			Union(u, v);
			ans += edges[i].weight;
		}
	}

	printf("%d\n", ans);

	return 0;
}

Για το Γυμνάσιο:

Κώδικας: Επιλογή όλων

#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

//#define LOCAL
#ifdef LOCAL
	#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
	#define DEBUG(x) 
#endif

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

int col[1000005];
map<int, int> freq;

int main(){

	freopen("colors.in", "r", stdin);
	freopen("colors.out", "w", stdout);

	int n, k;
	cin >> n >> k;

	for(int i = 0; i < n; i++) cin >> col[i];

	int l = 0, count = 0, ans = 10000009;
	for(int i = 0; i < n; i++){
		if(freq[col[i]] == 0) count++;
		freq[col[i]]++;
		if(count == k){ // Eαν στο διαστημα [l, i] εχουμε ολα τα χρωματα
			while(freq[col[l]] > 1) freq[col[l]]--, l++; // Αυξανουμε το l οσο η συνθηκη διατηρειται 
			ans = min(ans, i - l + 1);
		}
	}

	if(ans == 10000009) cout << "0\n";
	else cout << ans << '\n';

	return 0;
}

BTW τα αποτελέσματα ποτε περίπου θα βγουν?

[infinity]

Βγήκαν τα αποτελέσματα! Πολλά συγχαρητήρια στους επιτυχόντες

[Κηπουρίδης]

Στο γυμνάσιο βλέπω έχετε βρει τη γραμμική λύση, συγχαρητήρια!

Σχετικά με το λύκειο, προσέξτε ότι κάνοντας Kruskal δε χρειάζεται να ταξινομήσετε κατά βάρος τις ακμές αφού το βάρος τους είναι πολύ μικρό (μέχρι 100). Αρκεί να κάνετε 100 πίνακες, έναν για κάθε διακριτό βάρος, και να βάλετε την κάθε ακμή στον κατάλληλο πίνακα.
Έτσι έχετε "ταξινομήσει" σε γραμμικό χρόνο, φεύγει λοιπόν το logN από την πολυπλοκότητα. Ο υπόλοιπος Kruskal τρέχει (στην πράξη) γραμμικά (στη θεωρία N*α(N) όπου α(Ν) είναι η inverse ackermann συνάρτηση, που για κάθε Ν που μπορείτε να φανταστείτε (πχ 2^(1.000.000.000.000) ) είναι μικρότερη του 5).

Θερμά συγχαρητήρια σε όλους τους διαγωνιζόμενους!