Σελίδα 1 από 1

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

Δημοσιεύτηκε: Τρί Μαρ 21, 2017 9:13 pm
από infinity
Εδώ μπορείτε να αναρτήσετε και να συζητήσετε τις λύσεις σας για τα προβλήματα της Β φάσης.

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

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

Δημοσιεύτηκε: Τετ Μαρ 22, 2017 3:55 am
από 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;
}

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

Δημοσιεύτηκε: Τετ Μαρ 22, 2017 5:06 pm
από 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 ;
}

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

Δημοσιεύτηκε: Τετ Μαρ 22, 2017 9:52 pm
από 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;
}

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

Δημοσιεύτηκε: Τετ Μαρ 22, 2017 10:29 pm
από 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 τα αποτελέσματα ποτε περίπου θα βγουν?

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

Δημοσιεύτηκε: Τρί Μαρ 28, 2017 2:04 pm
από infinity
Βγήκαν τα αποτελέσματα! Πολλά συγχαρητήρια στους επιτυχόντες :D

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

Δημοσιεύτηκε: Τρί Μαρ 28, 2017 4:27 pm
από Κηπουρίδης
Στο γυμνάσιο βλέπω έχετε βρει τη γραμμική λύση, συγχαρητήρια!

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

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