oj.uz

Submission #270673

# Submission time Handle Problem Language Result Execution time Memory
270673 2020-08-17T22:04:47 Z fivefourthreeone Izlet (COI19_izlet) C++17
43 / 100
 817 ms 74740 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 3001;
int dsu[mxN];
int find(int a) {
    return dsu[a]==a ? a : dsu[a] = find(dsu[a]);
}
bool merge(int a, int b) {
    a = find(a); b = find(b);
    if(a==b)return false;
    dsu[b] = a;
    return true;
}
int arr[mxN][mxN];
int n;
int cnt;
vector<ttgl> ans;
vector<int> adj[mxN];
int col[mxN];
bool dfs(int id, int st, int u, int p) {
    //cout<<id<<" "<<st<<" "<<u<<" "<<arr[id][u]<<" "<<arr[st][u]<<" "<<col[u]<<"\n";
    if((arr[id][u]==arr[st][u])&&col[u]) {
        col[id] = col[u];
        return true;
    }
    for(int v: adj[u]) {
        if(v^p) {
            if(dfs(id, st, v, u)) {
                return true;   
            }
        }
    }
    return false;
}
int ari_orz;
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>ari_orz;
    cin>>n;
    owo(i, 0, n) {
        owo(j, 0, n) { 
            cin>>arr[i][j];
        }
    }
    owo(i, 0, n) {
        dsu[i] = i;
    }
    //merge all same color
    owo(i, 0, n) {
        owo(j, 0, n) {
            if(i==j)continue;
            if(arr[i][j]==1&&merge(i, j)) {
                ans.senpai({i, j});
                adj[i].senpai(j);
                adj[j].senpai(i);
            }
        }
    }
    owo(i, 0, n) {
        owo(j, 0, n) {
            if(i==j)continue;
            if(arr[i][j]==2&&merge(i, j)) {
                ans.senpai({i, j});
                adj[i].senpai(j);
                adj[j].senpai(i);
            }
        }
    }
    owo(i, 0, n) {
        bool ok = false;
        for(int k: adj[i]) {
            ok|=dfs(i, k, k, i);
            if(ok)break;
        }
        if(!ok) {
            col[i] = ++cnt;
        }
        cout<<col[i]<<" ";
    }
    cout<<"\n";
    for(auto p: ans) {
        cout<<(p.first+1)<<" "<<(p.second+1)<<"\n";
    }
    
    return 0;
}

Compilation message

izlet.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
izlet.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 651 ms 53496 KB Output is correct
3 Correct 647 ms 53496 KB Output is correct
4 Correct 663 ms 53368 KB Output is correct
5 Correct 659 ms 53368 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 53616 KB Output is correct
2 Correct 660 ms 53484 KB Output is correct
3 Correct 814 ms 73908 KB Output is correct
4 Correct 817 ms 74740 KB Output is correct
5 Correct 623 ms 53496 KB Output is correct
6 Correct 698 ms 60504 KB Output is correct
7 Correct 489 ms 49400 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 651 ms 53496 KB Output is correct
3 Correct 647 ms 53496 KB Output is correct
4 Correct 663 ms 53368 KB Output is correct
5 Correct 659 ms 53368 KB Output is correct
6 Correct 624 ms 53616 KB Output is correct
7 Correct 660 ms 53484 KB Output is correct
8 Correct 814 ms 73908 KB Output is correct
9 Correct 817 ms 74740 KB Output is correct
10 Correct 623 ms 53496 KB Output is correct
11 Correct 698 ms 60504 KB Output is correct
12 Correct 489 ms 49400 KB Output is correct
13 Incorrect 636 ms 54392 KB Output isn't correct
14 Halted 0 ms 0 KB -