oj.uz

Submission #114835

# Submission time Handle Problem Language Result Execution time Memory
114835 2019-06-03T12:23:22 Z shayan_p Airline Route Map (JOI18_airline) C++14
0 / 100
 701 ms 25476 KB 
// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include<Alicelib.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1111,lg=13;

vector<pii>v;

void Alice(int n,int m,int a[],int b[]){
    for(int i=0;i<n;i++){
	for(int j=0;j<lg;j++){
	    if(bit(i+1,j)) v.PB({i,j+n});
	}
    }
    for(int i=0;i<lg-1;i++){
	v.PB({n+i,n+i+1});
    }
    int N=n+lg,NN=lg+10;
    for(int i=N;i<N+NN;i++){
	for(int j=i+1;j<N+NN;j++){
	    v.PB({i,j});
	}
    }
    for(int i=0;i<n;i++){
	v.PB({N,i});
    }
    InitG(N+NN,m+sz(v));
    for(int i=0;i<m;i++){
	MakeG(i,a[i],b[i]);
    }
    for(int i=0;i<sz(v);i++){
	MakeG(i+m,v[i].F,v[i].S);
    }
}

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include<Boblib.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1111,lg=13;

bool bad[maxn];
int lab[maxn];

vector<int>v[maxn];
vector<pii>ans;

void solve(int u,int bt=0){
    bad[u]=1;
    int nxt=-1;
    for(int y:v[u]){
	if(bad[y])
	    lab[y]+= (1<<bt);
	else
	    nxt=y;
    }
    if(nxt!=-1) solve(nxt,bt+1);
}

void Bob(int n,int m,int a[],int b[]){
    for(int i=0;i<m;i++)
	v[a[i]].PB(b[i]), v[b[i]].PB(a[i]);
    int w=0;
    for(int i=0;i<n;i++){
	if(sz(v[i])>sz(v[w])) w=i;
    }
    bad[w]=1;
    for(int y:v[w]){
	bad[y]=1;
    }
    for(int i=0;i<n;i++){
	if(bad[i]) continue;
	int C=0;
	for(int y:v[i])
	    C+= !bad[y];
	if(C==1 && sz(v[i])!=1) solve(i);
    }
    int N=0,M=0;
    for(int i=0;i<m;i++){
	if(lab[a[i]]!=0 && lab[b[i]]!=0)
	    ans.PB( { lab[a[i]]-1, lab[b[i]]-1 } ),M++;
    }
    for(int i=0;i<n;i++){
	if(lab[i]!=0)
	    N++;
    }
    InitMap(N,M);
    for(pii p:ans){
	MakeMap(p.F,p.S);
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6752 KB Wrong Answer [10]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6752 KB Wrong Answer [10]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 701 ms 25476 KB Wrong Answer [10]
2 Halted 0 ms 0 KB -