oj.uz

Submission #158516

# Submission time Handle Problem Language Result Execution time Memory
158516 2019-10-17T14:03:34 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 1115 ms 69752 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;
            }
        }
        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 632 KB Output is correct
2 Correct 949 ms 41316 KB Output is correct
3 Correct 956 ms 38016 KB Output is correct
4 Correct 879 ms 37884 KB Output is correct
5 Correct 922 ms 37880 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 41412 KB Output is correct
2 Correct 899 ms 53492 KB Output is correct
3 Correct 1114 ms 68996 KB Output is correct
4 Correct 1115 ms 69752 KB Output is correct
5 Correct 883 ms 53432 KB Output is correct
6 Correct 932 ms 60536 KB Output is correct
7 Correct 686 ms 49400 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 949 ms 41316 KB Output is correct
3 Correct 956 ms 38016 KB Output is correct
4 Correct 879 ms 37884 KB Output is correct
5 Correct 922 ms 37880 KB Output is correct
6 Correct 966 ms 41412 KB Output is correct
7 Correct 899 ms 53492 KB Output is correct
8 Correct 1114 ms 68996 KB Output is correct
9 Correct 1115 ms 69752 KB Output is correct
10 Correct 883 ms 53432 KB Output is correct
11 Correct 932 ms 60536 KB Output is correct
12 Correct 686 ms 49400 KB Output is correct
13 Incorrect 896 ms 54364 KB Integer 0 violates the range [1, 3000]
14 Halted 0 ms 0 KB -