După ce eroii ninja l-au învins pe Nadakhan, de ziua celor dispăruți Zane trebuia să păzească cele n păpuși din muzeu. Între aceste păpuși există m coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele m coridoare Zane poate ajunge la fiecare dintre cele n păpuși. Skulkiu, având la dispoziție 5 tipuri de obstacole A, B, C, D, E, încearcă să-l oprească pe Zane punând pe fiecare coridor câte 4 obstacole. Zane poate distruge obstacolele de tip A, B, C și D, dar nu poate să distrugă obstacolele de tipul E. Pentru a distruge un obstacol de tipul A arma lui Zane are nevoie de 1 unitate de energie, pentru a distruge un obstacol de tipul B de 2 unități de energie, pentru a distruge un obstacol de tipul C de 3 unități de energie, iar pentru a distruge un obstacol de tipul D de 4 unități de energie. Datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, cele patru obstacole de pe acelaşi coridor au o adâncime din ce în ce mai mare, ceea ce implică faptul că pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de 5 ori mai multă energie decât cea obișnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de 25 ori mai multă energie decât cea obișnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 125 de ori mai multă energie decât cea obișnuită. Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi, aceasta depinzând doar de ordinea în care au fost amplasate obstacolele de către Skulkiu. Zane nu va înlătura obstacolele de pe toate coridoarele ci doar strictul necesar pentru a avea acces la fiecare păpușă. Zane dorește să-i lase pe ceilalți ninja să se antreneze așa că face în așa fel încât ajutorul pentru distrugerea obstacolelor de tip E să fie minim și apoi ca el să utilizeze un număr minim de unități de energie. Pentru coridoarele pe care se află obstacole de tip E Zane consumă energie doar pentru obstacolele de tip A, B, C şi D. Inițial Zane se află lângă păpușa 1.
Cerințe
- Precizați la câte dintre cele
npăpuși poate ajunge Zane înainte de a cere ajutorul celorlalți ninja. - Precizați pentru eliberarea câtor coridoare trebuie să ceară ajutor extern pentru a reuși să ajungă la toate cele
npăpuși și câte obstacole de tipEsunt în total pe aceste coridoare. - Precizați care este numărul minim de unități de energie utilizate.
Date de intrare
Fișierul de intrare ninjago.in conține pe prima linie v care poate avea doar valorile 1, 2 sau 3 reprezentând cerința care va fi rezolvată. Fișierul ninjago.in conține pe a doua linie numerele naturale n și m separate printr-un spațiu, iar pe următoarele m linii pentru fiecare coridor două numere naturale separate printr-un spațiu reprezentând cele două păpuși între care se circulă pe coridorul respectiv urmate de un spaţiu și patru litere corespunzătoare celor patru tipuri de obstacole în ordinea în care Skulkiu le-a amplasat pe coridorul respectiv. Între cele patru litere nu se află nici un spaţiu.
Date de ieșire
Dacă valoarea lui v este 1 atunci fișierul de ieșire ninjago.out va conține pe prima linie numai numărul păpușilor la care poate ajunge Zane înainte de a cere ajutorul celorlalți ninja.
Dacă valoarea lui v este 2 atunci fișierul de ieșire ninjago.out va conține pe prima linie numărul de coridoare pe care nu le poate elibera singur și pe a doua linie numărul total de obstacole de tip E de pe aceste coridoare.
Dacă valoarea lui v este 3 atunci fișierul de ieșire ninjago.out va conține pe prima linie numai numărul minim de unități de energie utilizate.
Restricții și precizări
1 ≤ N,M ≤ 31200;- Pentru rezolvarea corectă a primei cerințe se acordă 20 de puncte;
- Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 40 de puncte;
- Pentru rezolvarea corectă a celei de-a treia cerințe se acordă 30 de puncte.
- În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.
Exemplul 1
ninjago.in
1 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
5
Exemplul 2
ninjago.in
2 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
2 4
Exemplul 3
ninjago.in
3 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
1593
Explicații
Explicația exemplului 1
Zane va putea ajunge la nodurile 1, 2, 5, 6, 7. eliberând singur coridoarele (1,2), (1,5), (2,7) și (6,7)
Explicația exemplului 2
Zane trebuie să ceară ajutor pentru eliberarea a 2 coridoare pentru a putea ajunge la toate cele 9 păpuși.
După ce eroii ninja l-au învins pe Nadakhan, de ziua celor dispăruți Zane trebuia să păzească cele n păpuși din muzeu. Între aceste păpuși există m coridoare pe care se poate circula în ambele sensuri. Se garantează faptul că pe cele m coridoare Zane poate ajunge la fiecare dintre cele n păpuși. Skulkiu, având la dispoziție 5 tipuri de obstacole A, B, C, D, E, încearcă să-l oprească pe Zane punând pe fiecare coridor câte 4 obstacole. Zane poate distruge obstacolele de tip A, B, C și D, dar nu poate să distrugă obstacolele de tipul E. Pentru a distruge un obstacol de tipul A arma lui Zane are nevoie de 1 unitate de energie, pentru a distruge un obstacol de tipul B de 2 unități de energie, pentru a distruge un obstacol de tipul C de 3 unități de energie, iar pentru a distruge un obstacol de tipul D de 4 unități de energie. Datorită dispozitivului cu care Skulkiu amplasează obstacolele pe coridor, cele patru obstacole de pe acelaşi coridor au o adâncime din ce în ce mai mare, ceea ce implică faptul că pentru a distruge al doilea obstacol amplasat pe coridor este nevoie de 5 ori mai multă energie decât cea obișnuită, pentru a distruge cel de-al treilea obstacol amplasat pe coridor este nevoie de 25 ori mai multă energie decât cea obișnuită, iar pentru a distruge al patrulea obstacol amplasat pe acelaşi coridor este nevoie de 125 de ori mai multă energie decât cea obișnuită. Indiferent de sensul de parcurgere al coridorului de către Zane pentru a înlătura obstacolele, energia consumată este aceeaşi, aceasta depinzând doar de ordinea în care au fost amplasate obstacolele de către Skulkiu. Zane nu va înlătura obstacolele de pe toate coridoarele ci doar strictul necesar pentru a avea acces la fiecare păpușă. Zane dorește să-i lase pe ceilalți ninja să se antreneze așa că face în așa fel încât ajutorul pentru distrugerea obstacolelor de tip E să fie minim și apoi ca el să utilizeze un număr minim de unități de energie. Pentru coridoarele pe care se află obstacole de tip E Zane consumă energie doar pentru obstacolele de tip A, B, C şi D. Inițial Zane se află lângă păpușa 1.
Cerințe
- Precizați la câte dintre cele
npăpuși poate ajunge Zane înainte de a cere ajutorul celorlalți ninja. - Precizați pentru eliberarea câtor coridoare trebuie să ceară ajutor extern pentru a reuși să ajungă la toate cele
npăpuși și câte obstacole de tipEsunt în total pe aceste coridoare. - Precizați care este numărul minim de unități de energie utilizate.
Date de intrare
Fișierul de intrare ninjago.in conține pe prima linie v care poate avea doar valorile 1, 2 sau 3 reprezentând cerința care va fi rezolvată. Fișierul ninjago.in conține pe a doua linie numerele naturale n și m separate printr-un spațiu, iar pe următoarele m linii pentru fiecare coridor două numere naturale separate printr-un spațiu reprezentând cele două păpuși între care se circulă pe coridorul respectiv urmate de un spaţiu și patru litere corespunzătoare celor patru tipuri de obstacole în ordinea în care Skulkiu le-a amplasat pe coridorul respectiv. Între cele patru litere nu se află nici un spaţiu.
Date de ieșire
Dacă valoarea lui v este 1 atunci fișierul de ieșire ninjago.out va conține pe prima linie numai numărul păpușilor la care poate ajunge Zane înainte de a cere ajutorul celorlalți ninja.
Dacă valoarea lui v este 2 atunci fișierul de ieșire ninjago.out va conține pe prima linie numărul de coridoare pe care nu le poate elibera singur și pe a doua linie numărul total de obstacole de tip E de pe aceste coridoare.
Dacă valoarea lui v este 3 atunci fișierul de ieșire ninjago.out va conține pe prima linie numai numărul minim de unități de energie utilizate.
Restricții și precizări
1 ≤ N,M ≤ 31200;- Pentru rezolvarea corectă a primei cerințe se acordă 20 de puncte;
- Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 40 de puncte;
- Pentru rezolvarea corectă a celei de-a treia cerințe se acordă 30 de puncte.
- În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.
Exemplul 1
ninjago.in
1 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
5
Exemplul 2
ninjago.in
2 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
2 4
Exemplul 3
ninjago.in
3 9 15 1 2 CBAA 1 5 ABAA 2 6 CBEA 2 7 ACBA 2 5 CBEA 3 4 ABAA 3 7 AECE 3 8 CBAC 3 9 ECEE 4 8 DBAD 4 9 ECEB 5 6 CBAD 5 7 BAAD 6 7 CBAA 7 8 ECEB
ninjago.out
1593
Explicații
Explicația exemplului 1
Zane va putea ajunge la nodurile 1, 2, 5, 6, 7. eliberând singur coridoarele (1,2), (1,5), (2,7) și (6,7)
Explicația exemplului 2
Zane trebuie să ceară ajutor pentru eliberarea a 2 coridoare pentru a putea ajunge la toate cele 9 păpuși.
Zane are nevoie de ajutor pentru a elibera coridoarele (3,7) și (4,9). Pe fiecare dintre aceste 2 coridoare se află câte 2 obstacole de tip E, deci în total 4 obstacole de tip E.
Explicația exemplului 3
Zane va consuma minim 1593 de unități de energie astfel:
163pentru coridorul(1,2)161pentru coridorul(1,5)191pentru coridorul(2,7)161pentru coridorul(3,4)76pentru coridorul(3,7)413pentru coridorul(3,8)265pentru coridorul(4,9)163pentru coridorul(6,7)
Pentru coridorul (4,9) obstacolele sunt ECEB, deci Zane va consuma 0+3*5+0*25+2*125=265 unități de energie.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("ninjago.in");
ofstream cout("ninjago.out");
int n , m , x , y , cer , cost , v[31205] , T[31205] , cnt , nrm;
vector <int> G[31205];
vector <pair<int , int>> GR[31205];
char a , b , c , d;
struct poz
{
int i , j , w , areE;
}M[31205];
poz A[31205];
void dfs(int nod)
{
v[nod] = 1;
for(auto i : G[nod])
if(!v[i]) v[i] = 1 , dfs(i);
}
bool comp(poz a , poz b)
{
return a.w < b.w;
}
int radacina(int a)
{
if(a == T[a]) return a;
else return T[a] = radacina(T[a]);
}
int leaga(int a , int b)
{
if(T[a] > T[b]) T[a] = T[b];
else T[b] = T[a];
}
void kruskal()
{
int r1 , r2;
for(int i = 1 ; i <= m ; i++)
{
r1 = radacina(M[i].i);
r2 = radacina(M[i].j);
if(r1 != r2)
{
nrm++;
A[nrm] = M[i];
leaga(r1 , r2);
}
}
}
int main()
{
cin >> cer >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
cin >> M[i].i >> M[i].j >> a >> b >> c >> d;
cost = 0;
if(a != 'E' && b != 'E' && c != 'E' && d != 'E')
{
G[M[i].i].push_back(M[i].j);
G[M[i].j].push_back(M[i].i);
cost = (a - 'A' + 1) + 5 * (b - 'A' + 1) + 25 * (c - 'A' + 1) + 125 * (d - 'A' + 1);
M[i].areE = 0;
}
else
{
if(a != 'E')
cost += (a - 'A' + 1);
if(b != 'E')
cost += 5 * (b - 'A' + 1);
if(c != 'E')
cost += 25 * (c - 'A' + 1);
if(d != 'E')
cost += 125 * (d - 'A' + 1);
int nr = 0;
if(a == 'E') nr++;if(b == 'E') nr++;if(c == 'E') nr++;if(d == 'E') nr++;
M[i].areE = nr;
cost += 1000 * nr;
}
M[i].w = cost;
}
if(cer == 1)
{
dfs(1);
int cnt = 0;
for(int i = 1 ; i <= n ; i++)
if(v[i] != 0) cnt++;
cout << cnt;
}
else
{
for(int i = 1 ; i <= n ; i++)
T[i] = i;
sort(M + 1 , M + m + 1 , comp);
kruskal();
int p = 0 , sum = 0 , cateE = 0;;
for(int i = 1 ; i <= nrm ; i++)
{
if(A[i].areE > 0) p++ , cateE += A[i].areE;
sum += A[i].w - A[i].areE * 1000;
}
if(cer == 2) cout << p << '\n' << cateE;
else cout << sum;
}
}
