oj.uz

Submission #158521

# Submission time Handle Problem Language Result Execution time Memory
158521 2019-10-17T14:42:14 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 2000 ms 36152 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstring>
#define DIM 3005
using namespace std;
int tip, n, i, j, nr, nod;
int a[DIM][DIM], s[DIM], t[DIM], viz[DIM], w[DIM], ff[DIM];
vector<int> v[DIM];
int cmp(int x, int y){
    if(a[1][x] == a[1][y]){
        return x < y;
    }
    return a[1][x] < a[1][y];
}
void dfs(int curr, int nr){
    viz[curr] = 1;
    ff[ s[curr] ]++;
    if(ff[ s[curr] ] == 1){
        nr++;
    }
    if(a[curr][nod] == nr && s[nod] == 0){
        s[nod] = s[curr];
    }
    for(int i = 0; i < v[curr].size(); i++){
        int vecin = v[curr][i];
        if(viz[vecin] == 0){
            dfs(vecin, nr);
        }
    }
    ff[ s[curr] ]--;
}
void adauga(int x, int y){
    v[x].push_back(y);
    v[y].push_back(x);
}
int main(){
    scanf("%d%d", &tip, &n);
    for(i = 1; i <= n; i++){
        w[i] = i;
        for(j = 1; j <= n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    sort(w + 1, w + n + 1, cmp);
    s[1] = nr = 1;
    for(i = 2; i <= n; i++){
        nod = w[i];
        for(j = i - 1; j >= 1; j--){
            if(a[1][ w[j] ] == a[1][nod] && a[ w[j] ][nod] == 1){
                s[nod] = s[ w[j] ];
                t[nod] = w[j];
                adauga(t[nod], nod);
                break;
            }
        }
        if(s[nod] != 0){
            continue;
        }
        for(j = 1; j < i; j++){
            if(a[ w[j] ][nod] == 2){
                t[nod] = w[j];
                adauga(t[nod], nod);
                break;
            }
        }
        if(t[nod] == 0){
            for(j = i + 1; j <= n; j++){
                if(a[nod][ w[j] ] == 2){
                    swap(w[i], w[j]);
                    break;
                }
            }
            i--;
            continue;
        }
        memset(viz, 0, sizeof(viz) );
        memset(ff, 0, sizeof(ff) );
        viz[nod] = 1;
        dfs(t[nod], 0);
        if(s[nod] == 0){
            s[nod] = ++nr;
        }
    }
    for(i = 1; i <= n; i++){
        cout<< s[i] <<" ";
    }
    cout<<"\n";
    for(i = 2; i <= n; i++){
        cout<< i <<" "<< t[i] <<"\n";
    }
}

Compilation message

izlet.cpp: In function 'void dfs(int, int)':
izlet.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[curr].size(); i++){
                    ~~^~~~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &tip, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 914 ms 36060 KB Output is correct
3 Correct 912 ms 35836 KB Output is correct
4 Correct 858 ms 36080 KB Output is correct
5 Correct 890 ms 35728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 36084 KB Output is correct
2 Correct 862 ms 35812 KB Output is correct
3 Correct 1086 ms 36088 KB Output is correct
4 Correct 1142 ms 36152 KB Output is correct
5 Correct 839 ms 35980 KB Output is correct
6 Correct 892 ms 36040 KB Output is correct
7 Correct 646 ms 30412 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 914 ms 36060 KB Output is correct
3 Correct 912 ms 35836 KB Output is correct
4 Correct 858 ms 36080 KB Output is correct
5 Correct 890 ms 35728 KB Output is correct
6 Correct 924 ms 36084 KB Output is correct
7 Correct 862 ms 35812 KB Output is correct
8 Correct 1086 ms 36088 KB Output is correct
9 Correct 1142 ms 36152 KB Output is correct
10 Correct 839 ms 35980 KB Output is correct
11 Correct 892 ms 36040 KB Output is correct
12 Correct 646 ms 30412 KB Output is correct
13 Execution timed out 2052 ms 35736 KB Time limit exceeded
14 Halted 0 ms 0 KB -