I see many people solved this with graph algorithms, there is also greedy approach.

Let's build graph: u->v, if jedi u is winning v.
You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:36

Если вы используете DFS в итеративной форме,  то вы можете получить TLE#4.

Если вы перепишите DFS в рекурсивную форму и будете компилировать на Visual C++,  то получите AC за менее чем 0.1 секунды.

Короче,у нас проходит некий турнир.Правила таковы: мы выбираем любых двух джедаев из оставшихся ,они между собой сражаются,из них по условию ровно один побеждает,проигравший исчезает с турнира. И так далее: снова выбираем двух джедаев,один остается,и т.д. По условию либо Джедай А сильнее Джедая Б либо наоборот. Сильнее значит не менее чем по двум параметрам один джедай выигрывает у другого(т.е. соответствующие значения строго больше). Нам нужно найти всех возможных победителей,т.е. тех,кто останется последним. Мы можем как угодно формировать расписание турнира,т.е. выбирать кто с кем из оставшихся будет драться. Победитель может провести всего 1 бой,а может 2,а может 3,... .Расписание мы САМИ формируем!!!

У кого нет идей,советую узнать про алгоритм Тарьяна и граф конденсации.

Edited by author 31.08.2015 22:18

6
one 7 4 5
two 6 3 10
three 5 10 9
four 7 6 7
five 2 5 8
six 3 3 3

I think : one, two, three, four, five.

Edited by author 18.03.2009 20:44

3
q1 1 1 2
q2 1 2 1
q3 2 1 1

2
a1 1 1 1
a2 1 1 1

3
w1 6 6 6
w2 6 4 4
w3 5 5 5

great thanks!

Edited by author 11.08.2010 04:41

Сделайте нормальный человеческий перевод. Ну невозможно читать этот бред.
"Are different the lightsaber, and Jedi different are" - вот как это понять, или
" If looses a Jedi, must leave the tournament he." -
лучше условие на русском сделайте, чем бредовое английское.

#include<iostream>
#include<string>
#include<vector>
using namespace std;

struct node
{
    string name;
    bool flag[205],temp[205];
    vector<int> winto;
    int count ;    long int x, y,z;

    bool canWinOver(struct node p)
    {
        int c=0;
        if( x > p.x ) c++;
        if( y > p.y ) c++;
        if( z > p.z ) c++;

        if( c > 1 ) return true;
        return false;
    }
};

typedef struct node node;

int main()
{
    node jedi[205] ; int i , j , n , k , l;
    string s;
    long int p,q,r;
    cin >> n;

    for(i=1 ; i <= n ; i++ )
    {
        cin >> s >> p >> q >> r;

        jedi[i].name=s;    jedi[i].x=p;    jedi[i].y=q;    jedi[i].z=r;
    }

    for(i=1; i <= n ; i++)
    {
        for(j=i+1; j <= n ; j++)
        {
            if( jedi[i].canWinOver(jedi[j]) )
            {    jedi[i].flag[j]=true;    jedi[i].winto.push_back(j);        jedi[i].count++;    }
            else
            {    jedi[j].flag[i]=true;    jedi[j].winto.push_back(i);        jedi[j].count++;    }
        }
    }

    for(i=1 ; i <= n ; i++ )
    {
        for(j=1 ; j <= n ; j++ )
        {
            if(i!=j && !(jedi[i].flag[j]) )
            {
                for(k=0 ; k < jedi[i].count ; k++ )
                {
                    l = jedi[i].winto[k];
                    if(!(jedi[j].flag[l]))
                    {    jedi[j].winto.push_back(l);         jedi[j].temp[l]=true;            }
                }
            }
        }
    }

    for(i=1 ; i <= n ; i++ )
    {
        int sum=0;
            for(j=1 ; j <= n ; j++ )
            if( jedi[i].flag[j] || jedi[i].temp[j] )    sum++;

        if(sum==n-1)
        cout << jedi[i].name << endl;
    }

        return 0;

}


PLS HELP

I shocked! My program used 2 dfs(for find conecting components). Thats all. n<=200. Dfs work by O(n+m).
Why I have TL???
Please help me, I really dont understand, where my mistakes.

Be careful!!!
In the task said that "The parameters are ... not greater than 100000 by the ABSOLUTE value." So you need check not only if the letter, which in digit, is in ['0'..'9'], but '-' too.
GOOD LUCK and have AC )

I do not understand why at me the wrong answer 5.
Somebody can help{assist} me? Here my code.
Help{Assist} please, I cannot find my mistake{error}.
Thanks beforehand!!!

[code deleted]

Edited by moderator 23.06.2006 17:14

I do not understand why at me the wrong answer 5.
Somebody can help{assist} me? Here my code.
Help{Assist} please, I cannot find my mistake{error}.
Thanks beforehand!!!

[code deleted]

Edited by moderator 23.06.2006 17:18

i use bfs too!!!
i know no one will be patient to look over my code
so i do not put it out
or give me some texts!fu ck you very much~

Edited by author 14.11.2005 13:46

I suppose problem statement is not clear enought, because rules
for pair composing weren't stated. For me, for instance,
isn't obvious that one jedi of ,say, 500 can wait while others
kill each other and then kill the last one, so he can take part
only in one combat.
I thought first time that it is smth like olympic system, I mean.

program p1218;
const mx = 500;
var
 on,tw,th,good:array[1..mx] of longint;
 s:array[1..mx] of string;
 v:array[1..mx,1..mx] of boolean;
 n,k,i,j:integer;
 c:char;

function win(i,j:integer):boolean;
var
  res:integer;
begin
  res := byte(on[i] > on[j]) + byte(tw[i] > tw[j]) + byte(th[i] > th[j]);
  if res > 1 then win := True else win := False;
end;

function fill(j:integer):boolean;
var
  i:integer;
  b:boolean;
begin
  b := True;
  for i:=1 to n do
    b := b and v[j,i];
  if b then fill := True else fill := False;
end;

begin
  readln(n);
  for i:=1 to n do
  begin
   read(c); s[i]:='';
   repeat
    s[i] := s[i] + c;
    read(c);
   until c = ' ';
   readln(on[i],tw[i],th[i]);
  end;

  for i:=1 to n do
  for j:=1 to n do
    v[i,j] := win(i,j);

  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
       if not v[i,j] then v[i,j] := v[i,k] and v[k,j];

  for i:=1 to n do
   if fill(i) then writeln(s[i]);
end.

here is my program.
 1 i find  a jedi which cannot be beaten by another jedi with the
ekception of then some jedi which i already visited during DFS.
 2 this jedi can be the winner
 and also jedi which can be reached from this vertex in both sides
(can beat and be beaten)

 please mail your sugestions about this to p_s_@list.ru


THANKS IN ADVANCE!



VAR
  Name : ARRAY[1..510] OF String[32];
  w1,w,good : ARRAY[1..510] OF integer;

  Stat : ARRAY[1..510, 0..2] OF LongInt;
  a:array[1..510,1..510] of integer;
  N,m,point,num, I, J, Sum,l,i1,k : LongInt;
  S : String;
  Ok : Boolean;

  PROCEDURE init;
  VAR
    J,i : LongInt;
  BEGIN
   fillchar(a,sizeof(a),0);
   fillchar(good,sizeof(good),0);
   for i:=1 to n do
    for j:=1 to n do
     if (i<>j)and
      (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR
       ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR
       ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2])))
THEN
        begin
       a[i,j]:=1;
       inc(good[i]);
        end;

  END;
 procedure find(i:integer);
  var
  j,max:integer;
  f:boolean;
  begin
   j:=1;
   for i:=2 to n do
    if good[j]<good[i] then j:=i;
   k:=j;

  end;

procedure getting1;
var
 j,i:integer;
 t:array[1..501] of integer;
 f:boolean;
begin
 fillchar(t,sizeof(t),0);
 t[k]:=1;
  repeat
   f:=true;
   for i:=1 to n do
    if t[i]=1 then
     begin
      for j:=1 to n do
       if (a[i,j]=1)and(t[j]=0) then
        begin
         t[j]:=1;
         f:=false;
        end;
     end;
    if f then break;
  until false;
 for i:=1 to n do
  w[i]:=t[i];
end;


procedure getting2;
var
 j,i:integer;
 t:array[1..501] of integer;
 f:boolean;
begin
 fillchar(t,sizeof(t),0);
 t[k]:=1;
  repeat
   f:=true;
   for i:=1 to n do
    if t[i]=1 then
     begin
      for j:=1 to n do
       if (a[j,i]=1)and(t[j]=0) then
        begin
         t[j]:=1;
         f:=false;
        end;
     end;
    if f then break;
  until false;
 for i:=1 to n do
  w1[i]:=t[i];
end;



BEGIN
  ReadLn(N);

  FOR I := 1 TO N DO
    BEGIN
      ReadLn(S); S := S+' ';
      for j:=1 to length(s) do
       begin
        if (s[j]in['A'..'Z'])or(s[j] in ['a'..'z']) then
        begin
      insert(s[j],name[i],length(s));
       k:=j;
        end;
       end;
      Delete(S, 1, k);
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Sum := 0;
      WHILE (S[1]<>' ') DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Stat[I][0] := Sum;
      Sum := 0;
      WHILE (S[1]<>' ' ) DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Stat[I][1] := Sum;
      Sum := 0;
      WHILE (S[1]<>' ' ) DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      Stat[I][2] := Sum;
    END;
  init;
  ok:=false;
  fillchar(w,sizeof(w),0);
  find(1);
  fillchar(w,sizeof(w),0);
  fillchar(w1,sizeof(w1),0);
  getting1;
  getting2;

  for i:=1 to n do
   begin
    if (w[i]=1)and(w1[i]=1) then writeln(name[i]);
   end;


END.

VAR
  Name, Win : ARRAY[1..510] OF String[32];
  Flag, Killed : ARRAY[1..510] OF Byte;
  Stat : ARRAY[1..510, 0..2] OF LongInt;
  N, I, J, Sum : LongInt;
  S : String;
  Ok : Boolean;

  PROCEDURE Solve(I : LongInt);
  VAR
    J : LongInt;
  BEGIN
    IF Killed[I] = 1 THEN Exit;
    Killed[I] := 1;
    FOR J := 1 TO N DO
      IF (Killed[J] = 0) AND (I <> J) AND
      (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR
       ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR
       ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2]))) THEN
        BEGIN
          Solve(J);
        END;
  END;

BEGIN
  ReadLn(N);
  FillChar(Flag, SizeOf(Flag), 0);
  FOR I := 1 TO N DO
    BEGIN
      ReadLn(S); S := S+' ';
      Name[I] := Copy(S, 1, Pos(' ', S)-1);
      Delete(S, 1, Pos(' ', S));
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Sum := 0;
      WHILE (S[1] <> ' ') DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Stat[I][0] := Sum;
      Sum := 0;
      WHILE (S[1] <> ' ') DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      WHILE (S[1] = ' ') DO Delete(S, 1, 1);
      Stat[I][1] := Sum;
      Sum := 0;
      WHILE (S[1] <> ' ') DO
        BEGIN
          Sum := Sum*10+Ord(S[1])-Ord('0');
          Delete(S, 1, 1);
        END;
      Stat[I][2] := Sum;
    END;
  FOR I := 1 TO N DO
    BEGIN
      FillChar(Killed, SizeOf(Killed), 0);
      Solve(I);
      Ok := True;
      FOR J := 1 TO N DO
        IF Killed[J] = 0 THEN Ok := False;
      IF Ok THEN Flag[I] := 1;
    END;
  Sum := 0;
  FOR I := 1 TO N DO
    IF Flag[I] = 1 THEN
      BEGIN
        Inc(Sum);
        Win[Sum] := Name[I]
      END;
  FOR I := 1 TO Sum-1 DO WriteLn(Win[I]);
  Write(Win[Sum]);
END.

Why this WA, Plz Help!
----------------------------------------------------------------------
program a1218;

const
     max=502;

type
    xlist=integer;
    list=array[1..max]of xlist;
    atype=array[1..3]of list;
    gtype=array[1..max,1..max]of integer;
    ctype=array[1..max]of integer;

var
   name:array[1..max]of string;
   a:atype;
   b:list;
   g:gtype;
   c:ctype;
   i,j,n,j1,k:integer;
   s:shortint;
   st1,st2:string;
   ti:boolean;

procedure qsort(var a : ctype;lo,hi:integer);

    procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

    begin
       sort(lo,hi);
    end;

function inarr(x:integer;var s:integer;t:integer):boolean;
         var
            i,s1,t1:integer;
         begin
              s1:=s;t1:=t;inarr:=false;
              for i:=s1 to t1 do if c[i]=x then begin
                  s:=i;
                  inarr:=true;
                  exit;
              end;
         end;

procedure printf(s,t:integer);
          var
             i:integer;
          begin
               qsort(c,s,t);
               for i:=s to t do writeln(name[c[i]]);
          end;

procedure findcyc(x,dep:integer);
          begin
               for i:=1 to b[x] do begin
                   j:=1;
                   if inarr(g[x,i],j,dep) then begin
                      printf(j,dep);
                      halt;
                   end else begin
                       inc(dep);
                       c[dep]:=g[x,i];
                       findcyc(g[x,i],dep);
                       c[dep]:=0;
                       dec(dep);
                   end;
               end;
          end;

begin

     fillchar(a,sizeof(a),0);

     readln(n);
     for i:=1 to n do begin
         readln(st1);
         st2:='';
         for j:=1 to length(st1) do
             if st1[j]<>' ' then st2:=st2+st1[j] else break;
         name[i]:=st2;
         j1:=j;k:=0;
         for j:=j1 to length(st1) do if st1[j]=' ' then inc(k) else a
[k][i]:=a[k][i]*10+ord(st1[j])-48;
     end;

     fillchar(b,sizeof(b),0);
     for i:=1 to n do
         for j:=1 to n do begin
             s:=0;
             for k:=1 to 3 do if a[k][j]>a[k][i] then s:=s+1;
             if s>=2 then begin
                inc(b[i]);
                g[i,b[i]]:=j;
             end;
         end;

     ti:=true;
     for i:=1 to n do
         if b[i]=0 then begin
            writeln(name[i]);
            ti:=false;
         end;

     if ti then begin
        c[1]:=1;
        findcyc(1,1);
     end;

end.