oj.uz

답안 #173857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173857 2020-01-05T15:18:25 Z alexandra_udristoiu Izlet (COI19_izlet) C++14
43 / 100
 1087 ms 74044 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){
            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(j = i - 1; j >= 1; j--){
                if(t[ w[j] ] == 0 && a[ w[i] ][ w[j] ] == 2){
                    t[ w[j] ] = w[i];
                    nod = w[j];
                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 919 ms 53404 KB Output is correct
3 Correct 921 ms 53624 KB Output is correct
4 Correct 847 ms 53436 KB Output is correct
5 Correct 895 ms 53316 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 958 ms 53428 KB Output is correct
2 Correct 867 ms 53600 KB Output is correct
3 Correct 1074 ms 73312 KB Output is correct
4 Correct 1087 ms 74044 KB Output is correct
5 Correct 846 ms 53596 KB Output is correct
6 Correct 910 ms 60520 KB Output is correct
7 Correct 649 ms 49332 KB Output is correct

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 919 ms 53404 KB Output is correct
3 Correct 921 ms 53624 KB Output is correct
4 Correct 847 ms 53436 KB Output is correct
5 Correct 895 ms 53316 KB Output is correct
6 Correct 958 ms 53428 KB Output is correct
7 Correct 867 ms 53600 KB Output is correct
8 Correct 1074 ms 73312 KB Output is correct
9 Correct 1087 ms 74044 KB Output is correct
10 Correct 846 ms 53596 KB Output is correct
11 Correct 910 ms 60520 KB Output is correct
12 Correct 649 ms 49332 KB Output is correct
13 Incorrect 866 ms 54300 KB Output isn't correct
14 Halted 0 ms 0 KB -