oj.uz

Submission #144262

# Submission time Handle Problem Language Result Execution time Memory
144262 2019-08-16T12:03:32 Z Abelyan Izlet (COI19_izlet) C++17
43 / 100
 819 ms 40400 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=3e3+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

int qan[N][N],par[N],ans[N];
bool col[N];

int get(int v){
    if (par[v]==v)return v;
    return par[v]=get(par[v]);
}

void unite(int a,int b){
    a=get(a);
    b=get(b);
    if (a!=b){
        if (b>a)swap(a,b);
        par[a]=b;
    }
}

int main(){
    fastio;
    srng;
    int tp;
    cin>>tp;
    if (tp==1){
        int n;
        cin>>n;
        FORT(i,1,n)par[i]=i;
        FORT(i,1,n){
            FORT(j,1,n){
                cin>>qan[i][j];
                if (qan[i][j]==1)unite(i,j);
            }
        }
        FORT(i,1,n){
            if (get(i)==1)cout<<1<<" ";
            else cout<<2<<" ";
        }
        cout<<endl;
        FORT(i,1,n){
            if (i!=get(i))
                cout<<i<<" "<<get(i)<<endl;
        }
        FORT(i,2,n){
            int k=get(i);
            if (k==1 || col[k])continue;
            col[k]=true;
            cout<<1<<" "<<k<<endl;
        }
    }
    if (tp==2){
        int cnt=1;
        int n;
        cin>>n;

        //assert(n==5);
        FORT(i,1,n){
            FORT(j,1,n){
                cin>>qan[i][j];
            }
            int piti=0;
            FORTD(j,i-1,1){
                if (col[ans[j]])continue;
                col[ans[j]]=true;
                piti++;
                if (qan[i][j]==piti){
                    ans[i]=ans[j];
                    break;
                }

                //cout<<ans[i]<<" "<<piti<<endl;
            }
            FORT(i,1,n)col[i]=false;
            if (ans[i]==0)ans[i]=cnt++;
        }
        FORT(i,1,n)cout<<ans[i]<<" ";
        cout<<endl;
        FORT(i,2,n){
            cout<<i-1<<" "<<i<<endl;
        }
    }
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 649 ms 35768 KB Output is correct
3 Correct 626 ms 35808 KB Output is correct
4 Correct 621 ms 35828 KB Output is correct
5 Correct 620 ms 35800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 35780 KB Output is correct
2 Correct 612 ms 40056 KB Output is correct
3 Correct 812 ms 39704 KB Output is correct
4 Correct 819 ms 39556 KB Output is correct
5 Correct 630 ms 40400 KB Output is correct
6 Correct 673 ms 39388 KB Output is correct
7 Correct 503 ms 34168 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 649 ms 35768 KB Output is correct
3 Correct 626 ms 35808 KB Output is correct
4 Correct 621 ms 35828 KB Output is correct
5 Correct 620 ms 35800 KB Output is correct
6 Correct 635 ms 35780 KB Output is correct
7 Correct 612 ms 40056 KB Output is correct
8 Correct 812 ms 39704 KB Output is correct
9 Correct 819 ms 39556 KB Output is correct
10 Correct 630 ms 40400 KB Output is correct
11 Correct 673 ms 39388 KB Output is correct
12 Correct 503 ms 34168 KB Output is correct
13 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -