ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1022. Genealogical Tree

Can you explain this test?
Posted by Khujamurod 14 Jul 2017 12:26
Help! I dont understand that problem.
test:
3
0
1 0
0
can you explain which one is right ?
2 1 3
or
3 2 1
Re: Can you explain this test?
Posted by Khujamurod 14 Jul 2017 12:27
In addition I get WA6 and this is my code :
/*
#include <stdio.h>
#define maxn 105

int vp[maxn], pv[maxn];

int main() {

    int n, x, y;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        vp[i] = i;
        pv[i] = i;
    }
    for (int i = 1; i <= n; i ++) {
        int min = vp[i];
        while(1) {
            scanf("%d", &x);
            if(x == 0) break;
            if(vp[x] < min) min = vp[x];
        }
        for (int j = i - 1; j >= min; j --) {
            pv[j + 1] = pv[j];
            vp[pv[j + 1]] = j + 1;
        }
        pv[min] = i;
        vp[i] = min;
    }
    for (int i = 1; i <= n; i ++) {
        printf("%d ", pv[i]);
    }
    return 0;
}
*/
Re: Can you explain this test?
Posted by Mahilewets 14 Jul 2017 12:39
My AC program gives "3 2 1".
So, probably "3 2 1"  is the right answer.
Re: Can you explain this test?
Posted by Mahilewets 14 Jul 2017 12:42
I don't understand what your code does.
Probably intended solution uses an algorithm calling "topological sorting".  (My solution uses it too).
By definition,  topological sorting solves the task 1022.
Re: Can you explain this test?
Posted by Khujamurod 14 Jul 2017 12:44


Edited by author 14.07.2017 12:44
Re: Can you explain this test?
Posted by Khujamurod 14 Jul 2017 12:44
Yeah you are right. It is not an algorithm. It is just an idea but i think this idea  should accept!
Re: Can you explain this test?
Posted by Mahilewets 14 Jul 2017 12:45
In topological sorting,  you are doing depth first search and memorize vertices when you leave them.
When all the vertices are considered,  you have memorized vertices  in reversed topological sorted order.

Edited by author 14.07.2017 12:45
Re: Can you explain this test?
Posted by Mahilewets 14 Jul 2017 13:34
Yes,  I made a mistake.
Correct would be something like.

Intended solution is a program that calculates topological sort of vertices of a graph built from input data using some well-known algorithm for calculating topological sorting
Re: Can you explain this test?
Posted by Husayn Hasanov 19 Sep 2017 15:55
If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them!!! ;) ;/
Re: Can you explain this test?
Posted by Husayn Hasanov 19 Sep 2017 15:59
You should all do just DFS!(How? Just enter any node and check its adjacents were visited. So that enter node which was not visited before. Finally, put this node to array after checking and reverse the answer array)!

Edited by author 19.09.2017 16:04
Re: Can you explain this test?
Posted by Husayn Hasanov 19 Sep 2017 16:00
void dfs(int nd)
{
    for(int to : adj[nd])
        if(!used[to])
            dfs(to);
    used[nd] = true;    //switch the node into visited
    ans.push_back(nd);  //put the node to array
}

Edited by author 19.09.2017 16:03