oj.uz

답안 #144160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144160 2019-08-16T08:27:14 Z LeMur Izlet (COI19_izlet) C++14
18 / 100
 854 ms 36056 KB 
////////////////////////////////////////////    _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 3005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int t;
int n;
int a[N][N];

vector <int> g[N];
int answ[N];

vector < pair<int,int> > edge;
bool mark[N];
int used[N];

int main(){
	mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> t;
    cin >> n;
    int s = 0 , id;
    for(int i=1;i<=n;i++){
        int mx = 0;
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            mx = max(mx , a[i][j]);
        }
        if(mx > s){
            s = mx;
            id = i;
        }
    }
    for(int i=1;i<=n;i++){
        g[ a[id][i] ].push_back(i);
        answ[i] = a[id][i];
    }
    for(int i=1;i<=n;i++){
        if(answ[i] != s)continue;
        for(int j=1;j<=n;j++){
            if(a[i][j] == 2 || a[i][j] == 1){
                assert(answ[j] >= s - 1 && answ[j] <= s);
            }
        }
    }
    for(int i=1;i<=s;i++){
        int col = 0;
        int it = 0;
        while(it < (int)g[i].size()){
            ++col;
            int v = g[i][it];
            bool T = false;
            while(true){
                used[v] = col;
                bool flag = false;
                int go = -1;
                for(int h=0;h<(int)g[i].size();h++){
                    int p = g[i][h];
                    if(used[p] == used[v])continue;
                    if(a[v][p] != 1)continue;
                    if(used[p]){
                        edge.push_back(make_pair(v , p));
                        T = true;
                        break;
                    }
                    go = p;
                }
                if(T)break;
                if(!flag){
                    for(int j=0;j<(int)g[i - 1].size();j++){
                        int p = g[i - 1][j];
                        if(a[v][p] == 2){
                            edge.push_back(make_pair(v , p));
                            flag = true;
                            break;
                        }
                    }
                    if(flag == false){
                        if(i == 1)break;
                        if(go == -1){
                            for(int j=1;j<=n;j++){
                                if(a[go][j] == 2 && answ[j] == i + 1){
                                    edge.push_back(make_pair(v , go));
                                    break;
                                }
                            }
                            break;
                        }
                        else{
                            edge.push_back(make_pair(v , go));
                            v = go;
                        }
                    }
                    else
                        break;
                }
            }
            while(it < (int)g[i].size() && used[ g[i][it] ]){
                ++it;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout << answ[i] << " ";
    }
    cout << endl;
    //assert((int)edge.size() == n - 1);
    for(int i=0;i<n-1;i++){
        cout << edge[i].first << " " << edge[i].second << endl;
    }
    return 0;
}
/*
2
4
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
*/

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~
izlet.cpp:107:40: warning: array subscript is below array bounds [-Warray-bounds]
                                 if(a[go][j] == 2 && answ[j] == i + 1){
                                    ~~~~^
izlet.cpp:61:26: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
         answ[i] = a[id][i];
                   ~~~~~~~^

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 854 ms 36056 KB Output is correct
3 Correct 839 ms 35940 KB Output is correct
4 Correct 830 ms 35960 KB Output is correct
5 Correct 837 ms 35700 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 841 ms 35856 KB Integer 8208 violates the range [1, 3000]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 854 ms 36056 KB Output is correct
3 Correct 839 ms 35940 KB Output is correct
4 Correct 830 ms 35960 KB Output is correct
5 Correct 837 ms 35700 KB Output is correct
6 Incorrect 841 ms 35856 KB Integer 8208 violates the range [1, 3000]
7 Halted 0 ms 0 KB -