oj.uz

Submission #678160

# Submission time Handle Problem Language Result Execution time Memory
678160 2023-01-05T09:15:03 Z ibm2006 Airline Route Map (JOI18_airline) C++14
22 / 100
 755 ms 55952 KB 
#include "Alicelib.h"
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,m,i,j,a[110000],b[110000],h[110000],x,y,s;
vector<ll> v[110000];
/*void InitG(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    n=x;  m=y;
}
void MakeG(ll z,ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    v[x].push_back(y);
    v[y].push_back(x);
    h[x]++;
    h[y]++;
}*/
void Alice(ll N,ll M,ll A[],ll B[] ){
    if(N<=10)
    {
ll n,m,i,j;
	vector<ll> v[1100];
	vector<pair<ll,ll>> p;
	n=N+6;
	m=M;
	for(i=0;i<m;i++)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        s++;
        p.push_back({A[i],B[i]});
    }
    for(i=0;i<n;i++)
    {
        v[i].push_back(n);
        v[n].push_back(i);
        p.push_back({i,n});
        s++;
    }
    for(i=0;i<n;i++)
    {
        x=i;
        for(j=0;j<4;j++)
        {
            if(x%2==1)
            {
                if(j==0)
                {v[i].push_back(n+j+1);  s++;  v[n+j+1].push_back(i);
                p.push_back({i,n+j+1});
                 }
                v[i].push_back(n+j+2);
                v[n+j+2].push_back(i);
                s++;
                p.push_back({i,n+j+2});
            }
            x/=2;
        }
    }
    for(i=1;i<4;i++)
    {
        v[n+i+2].push_back(n+i+1);
        v[n+i+1].push_back(n+i+2);
        p.push_back({n+i+1,n+i+2});
        s++;
    }
    v[n+1].push_back(n+3);
    v[n+3].push_back(n+1);
    p.push_back({n+1,n+3});
    s++;
	InitG(n+6,s);
	for(i=0;i<s;i++)
        MakeG(i,p[i].first,p[i].second);
    return;
    ////////////////////////
    }
	ll n,m,i,j;
	vector<ll> v[1100];
	vector<pair<ll,ll>> p;
	n=N;
	m=M;
	for(i=0;i<m;i++)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
        s++;
        p.push_back({A[i],B[i]});
    }
    for(i=0;i<n;i++)
    {
        v[i].push_back(n);
        v[n].push_back(i);
        p.push_back({i,n});
        s++;
    }
    for(i=0;i<n;i++)
    {
        x=i;
        for(j=0;j<10;j++)
        {
            if(x%2==1)
            {
                if(j==0)
                {v[i].push_back(n+j+1);  s++;  v[n+j+1].push_back(i);
                p.push_back({i,n+j+1});
                 }
                v[i].push_back(n+j+2);
                v[n+j+2].push_back(i);
                s++;
                p.push_back({i,n+j+2});
            }
            x/=2;
        }
    }
    for(i=1;i<10;i++)
    {
        v[n+i+2].push_back(n+i+1);
        v[n+i+1].push_back(n+i+2);
        p.push_back({n+i+1,n+i+2});
        s++;
    }
    v[n+1].push_back(n+3);
    v[n+3].push_back(n+1);
    p.push_back({n+1,n+3});
    s++;
	InitG(n+12,s);
	for(i=0;i<s;i++)
        MakeG(i,p[i].first,p[i].second);
    return;
}
/*int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%lld %lld",&a[i],&b[i]);
    }
    Alice(n,m,a,b);
    for(i=0;i<n;i++)
    {
        printf("%lld: ",i);
        x=v[i].size();
        for(j=0;j<x;j++)
            printf("%lld ",v[i][j]);
        printf("\n");
    }
}
*/
#include "Boblib.h"
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll b[1100][1100],n,m,i,a[110000],c[110000];
vector<ll> v[110000];
/*void InitMap(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    n=x;  m=y;
}
void MakeMap(ll x,ll y)
{
    printf("%lld %lld\n",x,y);
    v[x].push_back(y);
    v[y].push_back(x);
}*/
void Bob( int V, int U, int C[], int D[] ){
    ll j;
    ll n,m,s,a[11000],c[11000],d[11000],h[11000],t,x,y,i;
       n=0;  m=0;  s=0;  t=0;
       for(i=0;i<11000;i++)
       {a[i]=0;  c[i]=0;  d[i]=0;  h[i]=0;  t=0; x=0;  y=0;}
    if(V<=22)
    {

	vector<ll> u;
	n=V;
	m=U;
	s=n-6;
	vector<ll> v[1100];
	vector<pair<ll,ll>> p;
	for(i=0;i<m;i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        b[C[i]][D[i]]=1;
        b[D[i]][C[i]]=1;
        h[C[i]]++;
        h[D[i]]++;
    }
    for(i=0;i<n;i++)
    {
        if(h[i]>=(s))
        {
            x=i;
            break;
        }
    }
  //  printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
    a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        {
            u.push_back(i);
           // printf("%lld\n",i);
                   }
    }
    for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {//printf("%lld ",u[i]);
            if(b[u[i]][u[j]]==1)
                a[u[i]]++;
        }
   // printf("\n");
    }
    for(i=0;i<5;i++)
    {//printf("%lld ",a[u[i]]);
        if(a[u[i]]==3)
        {
            x=u[i];
            d[2]=x;
        }
    }
  //  printf("%lld\n",x);
    for(i=0;i<5;i++)
    {
        if(b[u[i]][d[2]]==1&&a[u[i]]==1)
            d[1]=u[i];
    }
    for(i=3;i<=3;i++)
    {
        for(j=0;j<5;j++)
        {
            if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==2)
                d[i]=u[j];
        }
    }
    i=4;
    for(j=0;j<5;j++)
    {
        if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==1)
                d[i]=u[j];
    }
  /*  for(i=1;i<=4;i++)
        printf("%lld ",d[i]);
   */ for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<n;i++)
    {
        if(h[i]>=s)
        {
            x=i;
            break;
        }
    }
 //   printf("%lld ",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
   // a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        continue;
    x=1;  y=0;
        for(j=1;j<=4;j++)
        {
            if(b[i][d[j]]==1)
                y+=x;
            x*=2;
        }
        c[i]=y;
    }
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
    {
        if(a[i]+a[j]<=1)
            continue;

        if(b[i][j]==1)
       {

       p.push_back({c[i],c[j]});

       t++;}
    }
    InitMap(s-6,t);
    for(i=0;i<t;i++)
    MakeMap(p[i].first,p[i].second);
        return;
    }
/*	InitMap( 3, 2 );
	MakeMap( 1, 2 );
	MakeMap( 1, 3 );*/

	vector<ll> u;
	n=V;
	m=U;
	s=n-12;
	vector<ll> v[1100];
	vector<pair<ll,ll>> p;
	for(i=0;i<m;i++)
    {
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
        b[C[i]][D[i]]=1;
        b[D[i]][C[i]]=1;
        h[C[i]]++;
        h[D[i]]++;
    }
    for(i=0;i<n;i++)
    {
        if(h[i]>=s)
        {
            x=i;
            break;
        }
    }
  //  printf("%lld\n",x);
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
    a[x]=1;
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        {
            u.push_back(i);        }
    }
    for(i=0;i<11000;i++)
        a[i]=0;
    for(i=0;i<11;i++)
    {
        for(j=0;j<11;j++)
        {
            if(b[u[i]][u[j]]==1)
                a[u[i]]++;
        }
    }
    for(i=0;i<11;i++)
    {
        if(a[u[i]]==3)
        {
            x=u[i];
            d[2]=x;
        }
    }
    for(i=0;i<11;i++)
    {
        if(b[u[i]][d[2]]==1&&a[u[i]]==1)
            d[1]=u[i];
    }
    for(i=3;i<=9;i++)
    {
        for(j=0;j<11;j++)
        {
            if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==2)
                d[i]=u[j];
        }
    }
    i=10;
    for(j=0;j<11;j++)
    {
        if(d[i-2]!=u[j]&&b[d[i-1]][u[j]]==1&&a[u[j]]==1)
                d[i]=u[j];
    }
    for(i=0;i<n;i++)
        a[i]=0;
    for(i=0;i<n;i++)
    {
        if(h[i]>=s)
        {
            x=i;
            break;
        }
    }
    for(i=0;i<h[x];i++)
    {
        a[v[x][i]]=1;
    }
    for(i=0;i<n;i++)
    {
        if(a[i]==0)
        continue;
    x=1;  y=0;
        for(j=1;j<=10;j++)
        {
            if(b[i][d[j]]==1)
                y+=x;
            x*=2;
        }
        c[i]=y;
    }
     for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
    {
        if(a[i]+a[j]<=1)
            continue;

        if(b[i][j]==1)
       {

       p.push_back({c[i],c[j]});

       t++;}
    }
    InitMap(s,t);
    for(i=0;i<t;i++)
    MakeMap(p[i].first,p[i].second);
}
/*int main()
{
    scanf("%lld %lld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%lld %lld",&a[i],&c[i]);
    }
    Bob(n,m,a,c);
}*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10020 KB Output is correct
2 Correct 6 ms 10124 KB Output is correct
3 Correct 5 ms 10100 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct
5 Correct 6 ms 9960 KB Output is correct
6 Correct 5 ms 10032 KB Output is correct
7 Correct 5 ms 10104 KB Output is correct
8 Correct 5 ms 10236 KB Output is correct
9 Correct 5 ms 10044 KB Output is correct
10 Correct 5 ms 10120 KB Output is correct
11 Correct 5 ms 10132 KB Output is correct
12 Correct 5 ms 10056 KB Output is correct
13 Correct 5 ms 10124 KB Output is correct
14 Correct 7 ms 10124 KB Output is correct
15 Correct 5 ms 10120 KB Output is correct
16 Correct 5 ms 10104 KB Output is correct
17 Correct 5 ms 9948 KB Output is correct
18 Correct 5 ms 10100 KB Output is correct
19 Correct 5 ms 10160 KB Output is correct
20 Correct 5 ms 10124 KB Output is correct
21 Correct 5 ms 10160 KB Output is correct
22 Correct 5 ms 10104 KB Output is correct
23 Correct 5 ms 10124 KB Output is correct
24 Correct 5 ms 10120 KB Output is correct
25 Correct 5 ms 10108 KB Output is correct
26 Correct 5 ms 10052 KB Output is correct
27 Correct 6 ms 10124 KB Output is correct
28 Correct 5 ms 10124 KB Output is correct
29 Correct 5 ms 10116 KB Output is correct
30 Correct 5 ms 10120 KB Output is correct
31 Correct 6 ms 10064 KB Output is correct
32 Correct 5 ms 10120 KB Output is correct
33 Correct 5 ms 10220 KB Output is correct
34 Correct 6 ms 10120 KB Output is correct
35 Correct 5 ms 10128 KB Output is correct
36 Correct 5 ms 10132 KB Output is correct
37 Correct 5 ms 10124 KB Output is correct
38 Correct 5 ms 10044 KB Output is correct
39 Correct 6 ms 10132 KB Output is correct
40 Correct 6 ms 10128 KB Output is correct
41 Correct 5 ms 10124 KB Output is correct
42 Correct 6 ms 10044 KB Output is correct
43 Correct 5 ms 10124 KB Output is correct
44 Correct 7 ms 10120 KB Output is correct
45 Correct 5 ms 10060 KB Output is correct
46 Correct 5 ms 10056 KB Output is correct
47 Correct 5 ms 10012 KB Output is correct
48 Correct 5 ms 10016 KB Output is correct
49 Correct 6 ms 10188 KB Output is correct
50 Correct 6 ms 10120 KB Output is correct
51 Correct 5 ms 10120 KB Output is correct
52 Correct 5 ms 10124 KB Output is correct
53 Correct 6 ms 10044 KB Output is correct
54 Correct 6 ms 10112 KB Output is correct
55 Correct 5 ms 10132 KB Output is correct
56 Correct 5 ms 10044 KB Output is correct
57 Correct 6 ms 10124 KB Output is correct
58 Correct 5 ms 10128 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10020 KB Output is correct
2 Correct 6 ms 10124 KB Output is correct
3 Correct 5 ms 10100 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct
5 Correct 6 ms 9960 KB Output is correct
6 Correct 5 ms 10032 KB Output is correct
7 Correct 5 ms 10104 KB Output is correct
8 Correct 5 ms 10236 KB Output is correct
9 Correct 5 ms 10044 KB Output is correct
10 Correct 5 ms 10120 KB Output is correct
11 Correct 5 ms 10132 KB Output is correct
12 Correct 5 ms 10056 KB Output is correct
13 Correct 5 ms 10124 KB Output is correct
14 Correct 7 ms 10124 KB Output is correct
15 Correct 5 ms 10120 KB Output is correct
16 Correct 5 ms 10104 KB Output is correct
17 Correct 5 ms 9948 KB Output is correct
18 Correct 5 ms 10100 KB Output is correct
19 Correct 5 ms 10160 KB Output is correct
20 Correct 5 ms 10124 KB Output is correct
21 Correct 5 ms 10160 KB Output is correct
22 Correct 5 ms 10104 KB Output is correct
23 Correct 5 ms 10124 KB Output is correct
24 Correct 5 ms 10120 KB Output is correct
25 Correct 5 ms 10108 KB Output is correct
26 Correct 5 ms 10052 KB Output is correct
27 Correct 6 ms 10124 KB Output is correct
28 Correct 5 ms 10124 KB Output is correct
29 Correct 5 ms 10116 KB Output is correct
30 Correct 5 ms 10120 KB Output is correct
31 Correct 6 ms 10064 KB Output is correct
32 Correct 5 ms 10120 KB Output is correct
33 Correct 5 ms 10220 KB Output is correct
34 Correct 6 ms 10120 KB Output is correct
35 Correct 5 ms 10128 KB Output is correct
36 Correct 5 ms 10132 KB Output is correct
37 Correct 5 ms 10124 KB Output is correct
38 Correct 5 ms 10044 KB Output is correct
39 Correct 6 ms 10132 KB Output is correct
40 Correct 6 ms 10128 KB Output is correct
41 Correct 5 ms 10124 KB Output is correct
42 Correct 6 ms 10044 KB Output is correct
43 Correct 5 ms 10124 KB Output is correct
44 Correct 7 ms 10120 KB Output is correct
45 Correct 5 ms 10060 KB Output is correct
46 Correct 5 ms 10056 KB Output is correct
47 Correct 5 ms 10012 KB Output is correct
48 Correct 5 ms 10016 KB Output is correct
49 Correct 6 ms 10188 KB Output is correct
50 Correct 6 ms 10120 KB Output is correct
51 Correct 5 ms 10120 KB Output is correct
52 Correct 5 ms 10124 KB Output is correct
53 Correct 6 ms 10044 KB Output is correct
54 Correct 6 ms 10112 KB Output is correct
55 Correct 5 ms 10132 KB Output is correct
56 Correct 5 ms 10044 KB Output is correct
57 Correct 6 ms 10124 KB Output is correct
58 Correct 5 ms 10128 KB Output is correct
59 Incorrect 7 ms 10284 KB Wrong Answer [11]
60 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 755 ms 55952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -