Результати турніру "Практичні графи"

Зведена таблиця результатів

Учасник\Тест Haker Mapa Suma
0361_Ярослав Твердохлеб 45 50 95
0536_Артур Павленко 24 50 74
0196_Андрій Максай 15 50 65
0076_Богдан Потапський 35 0 35
0085_Дмитро Ігнатенко 35 0 35
0023_Іван Демчук 15 5 20

 

Результати тестів по задачі "Haker"

Учасник\Тест 01 02 03 04 05 06 07 08 09 10 Sum
0023_Іван Демчук - + + - - - + T T T 15,0
0076_Богдан Потапський + + + + + + + T T T 35,0
0085_Дмитро Ігнатенко + + + + + + + T T T 35,0
0196_Андрій Максай + + - + - - - - - - 15,0
0361_Ярослав Твердохлеб + + + + + + + + + - 45,0
0536_Артур Павленко P + P P P P - - - - 23,8

 

Результати тестів по задачі "Mapa"

Учасник\Тест 01 02 03 04 05 06 07 08 09 10 Sum
0023_Іван Демчук - + - - - - - - - - 5,0
0076_Богдан Потапський N N N N N N N N N N 0,0
0085_Дмитро Ігнатенко R R R R R R R R R R 0,0
0196_Андрій Максай + + + + + + + + + + 50,0
0361_Ярослав Твердохлеб + + + + + + + + + + 50,0
0536_Артур Павленко + + + + + + + + + + 50,0

 

Легенда:
T - перевищений ліміт часу
W - помилка вводу-виводу, використання модуля Crt.
R - помилка виконання
N - відсутній розв'язок
P - штраф за виведення лишнього символа або рядка

Розв"язки задач турніру

Haker

Автор: Твердохліб Ярослав

 

		#define _CRT_SECURE_NO_DEPRECATE
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 2*acos(0.0)
#define mp make_pair
#define x first
#define y second
#define sqr(a) (a)*(a)
#define D(a,b) sqrt(((a).x-(b).x)*((a).x-(b).x)+((a).y-(b).y)*((a).y-(b).y))
#define pii pair<int,int>
#define pdd pair<double,double>
#define sz(x) int((x).size())
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,n)
#define rept(i,n) FOR(i,0,n-1)
#define L(s) (int)((s).end()-(s).begin())
#define C(a) memset((a),0,sizeof(a))
#define val(ch) (int)(ch)-(int)('0')
#define toch(a) (char)((int)(a)+(int)('0'))
#define VI vector 
#define ll long long
int a,b,c,d,i,j,n,m,k,kol,lkol;
VI sm[10001],sm2[10001];
bitset <10001> used;
bitset <10001> cool;
bitset <10001> smezn;
int lst[10001];
int l[10001];
int nver[10001];
int numb[10001];
int mas[10001];
void dfs(int v)
{
	used[v]=true;
	rept(i,L(sm[v]))
	{
		int w=sm[v][i];
		if (!used[w]) dfs(w);
	}
	lst[kol++]=v;
}
void dfs2(int v)
{
	l[lkol++]=v; cool[v]=1;
	used[v]=true;
	rept(i,L(sm2[v]))
	{
		int w=sm2[v][i];
		if (!used[w]) dfs2(w);
	}
}
void dfs3(int v)
{
	smezn[nver[v]]=true;
	rept(i,L(sm[v]))
	{
		int w=nver[sm[v][i]];
		if (!used[w] && !smezn[w])
		{
			dfs3(w);
			mas[v]+=mas[w];
		} else 
			if (!smezn[w]) { mas[v]+=mas[w]; smezn[w]=1; }
	}
}
int main()
{
	freopen("haker.in","r",stdin);
	freopen("haker.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,m)
	{
		scanf("%d%d",&a,&b);
		sm[b].pb(a); sm2[a].pb(b);
	}
	kol=0; used.reset();
	rep(i,n)
	{
		if (!used[i]) dfs(i);
	}
	used.reset(); C(l); smezn.reset(); C(nver); C(numb);
	FORD(ii,n,1)
	{
		lkol=0;  
		if (!used[lst[ii-1]]) 
		{ 
			cool.reset(); 
			smezn.reset(); 
			dfs2(lst[ii-1]); 
		} 
		else continue;
		int jj=0;
		int i=lst[ii-1];
		while (jj<L(sm[i]))
		{
			int w=sm[i][jj];
			if (cool[w])
			{
				sm[i][jj]=sm[i][L(sm[i])-1];
				sm[i].ppb();
			} else	{ smezn[w]=1; jj++; }
		}
		rept(j,lkol)
		{
			int w=l[j];
			nver[w]=i;
			if (w==i) continue;
			rept(ar,L(sm[w]))
			{
				int u=sm[w][ar];
				if (!smezn[u] && !cool[u])
				{
					sm[i].pb(u); smezn[u]=1;
				}
			}
		}
		numb[i]=lkol;
	}
	cool.reset();
	rep(i,n)
	{
		rept(j,L(sm[i]))
		{
			cool[nver[sm[i][j]]]=1;
		}
		mas[i]=numb[nver[i]];
	}
	used.reset();
	rep(i,n) if (!cool[i] && nver[i]==i) 
	{
		smezn.reset();
		dfs3(i);
		used|=smezn;
	}
	a=*max_element(mas+1,mas+n+1);
	bool t=true;
	rep(i,n)
	{
		if (mas[i]==a && t) { printf("%d",i); t=false; } else if (mas[i]==a) printf(" %d",i);
	}
	printf("\n");
	fclose(stdin); fclose(stdout);
}
		
		

Задача "Mapa"

Автор: Павленко Артур

 

	/* DevC++ */

#include <fstream>


using namespace std;

int log[1002][1002],n,m,i,j,x,y,a,b,d,sum,way=0,answ=0;

void clean(int i,  int j)
{
     log[i][j]=0;
     log[j][i]=0;
}

void clean_array()
{
     for (int i=0;i<=n;i++)
     for (int j=0;j<=n;log[i][j++]=0);
}
     
         


int main(int argc, char *argv[])
{
    ifstream inf("mapa.in");
    ofstream off("mapa.out");
    inf>>n>>m;
    clean_array();
    for (i=0;i<m;i++)
    {
        inf>>a>>b>>d;
        log[a][b]=d;
        log[b][a]=d;
        log[0][a]++;
        log[0][b]++;
   }
   answ=m;
   for (i=1;i<=n; i++) if (log[0][i]==2) answ--;
   
   off<<answ<<endl;
   
   for (j=1; j<=n; j++)
   {
       x=0;y=0;
       
       if (log[0][j]==2) {      
       for (i=1;i<=n;i++) {
           
           if ((log[i][j])&&(x==0)) x=i;
           else if ((log[i][j])&&(y==0)) {
                y=i; sum=log[x][j]+log[y][j];
                clean(x,j); clean(y,j);
                log[0][j]=0;
                break;
                } //if
                } //for
       if ((log[x][y]) && (log[0][y]==2)) {
       log[x][x]=sum+log[x][y];
       clean(x,y); }
       else if ((log[x][y])&&(log[0][x]==2)) {
       log[y][y]=sum+log[x][y];
       clean(x,y); }
       else if (log[x][y]==0) { 
       log[x][y]=sum; log[y][x]=sum;
       }
       else if ((log[x][y]) && (log[0][y]>2)&&(log[0][x]>2)) {
            off<<x<<" "<<y<<" "<<sum<<endl;
           
           }
           }
            
}
    for (j=1; j<=n; j++)
     if (log[0][j])
     for (i=1;i<=n;i++)
      if (log[i][j]) {
                     if (i<j) off<<i<<" "<<j<<" "<<log[i][j]<<endl;
                     else off<<j<<" "<<i<<" "<<log[i][j]<<endl;
                     clean(i,j);
                     
                     } //end if
                     
     off.close();
     return 0;
   } //end