oj.uz

Submission #158519

# Submission time Handle Problem Language Result Execution time Memory
158519 2019-10-17T14:33:21 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 2000 ms 35996 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){
    if(s[nod] != 0){
        return;
    }
    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:29: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:42: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:46: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 846 ms 35832 KB Output is correct
3 Correct 849 ms 35948 KB Output is correct
4 Correct 807 ms 35900 KB Output is correct
5 Correct 824 ms 35808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 35928 KB Output is correct
2 Correct 828 ms 35960 KB Output is correct
3 Correct 1063 ms 35964 KB Output is correct
4 Correct 1102 ms 35996 KB Output is correct
5 Correct 813 ms 35956 KB Output is correct
6 Correct 848 ms 35972 KB Output is correct
7 Correct 622 ms 30480 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 846 ms 35832 KB Output is correct
3 Correct 849 ms 35948 KB Output is correct
4 Correct 807 ms 35900 KB Output is correct
5 Correct 824 ms 35808 KB Output is correct
6 Correct 837 ms 35928 KB Output is correct
7 Correct 828 ms 35960 KB Output is correct
8 Correct 1063 ms 35964 KB Output is correct
9 Correct 1102 ms 35996 KB Output is correct
10 Correct 813 ms 35956 KB Output is correct
11 Correct 848 ms 35972 KB Output is correct
12 Correct 622 ms 30480 KB Output is correct
13 Execution timed out 2055 ms 35704 KB Time limit exceeded
14 Halted 0 ms 0 KB -