oj.uz

Submission #991869

# Submission time Handle Problem Language Result Execution time Memory
991869 2024-06-03T10:01:11 Z simona1230 Airline Route Map (JOI18_airline) C++17
37 / 100
 231 ms 20232 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"

using namespace std;

void Alice(int n,int m,int a[],int b[])
{
    vector<pair<int,int> > v;
    int l[1024];
    int num=0;
    for(int i=0;i<n;i++)
    {
        int cnt=i+3;
        l[i]=num;

        for(int j=1;j<cnt;j++)
        {
            v.push_back({num,num+1});
            num++;
        }

        v.push_back({num,num-cnt+1});

        num++;
        v.push_back({l[i],num});
        l[i]=num;
        num++;
        //cout<<l[i]<<" ";
    }
    //cout<<endl;



    for(int i=0;i<m;i++)
    {
        v.push_back({l[a[i]],l[b[i]]});
    }

    //cout<<"* "<<num<<endl;

    InitG(num,v.size());
    for(int i=0;i<v.size();i++)
    {
        int x=min(v[i].first,v[i].second);
        int y=max(v[i].first,v[i].second);
        //cout<<x<<"  -  "<<y<<endl;
        MakeG(i,x,y);
    }
}

#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;

int x[100001],y[100001];
vector<int> e[100001];
int used[100001];
int l[100001];
int maxx=0;

void dfs(int i,int c,int bg,int p)
{
    //cout<<i<<"->"<<c<<endl;
    used[i]=1;
    for(int j=0;j<e[i].size();j++)
    {
        int nb=e[i][j];
        if(e[nb].size()==2&&nb!=p&&!used[nb])dfs(nb,c+1,bg,i);
        else if(nb!=p&&nb==bg)
        {
            maxx=max(maxx,c-2);
            for(int k=0;k<e[bg].size();k++)
            {
                if(used[e[bg][k]]!=1)
                {
                    //cout<<"in "<<e[bg][k]<<endl;
                    l[e[nb][k]]=c-2;
                    return;
                }
            }
        }
    }
    used[i]=2;
}

void Bob(int v,int u,int c[],int d[])
{
    //cout<<v<<" ------ "<<u<<endl;
    for(int i=0;i<u;i++)
    {
        e[c[i]].push_back(d[i]);
        e[d[i]].push_back(c[i]);
        //cout<<c[i]<<" "<<d[i]<<endl;
    }

    //cout<<v<<" ------ "<<u<<endl;
    for(int i=0;i<v;i++)
    {
        //cout<<v<<" "<<i<<"     "<<e[i].size()<<endl;
        if(e[i].size()==3)dfs(i,1,i,-1);
        //cout<<"out "<<endl;
    }

    vector<pair<int,int> > ans;
    for(int i=0;i<u;i++)
    {
        if(l[c[i]]&&l[d[i]])
            ans.push_back({l[c[i]]-1,l[d[i]]-1});
    }

    InitMap(maxx,ans.size());
    for(int i=0;i<ans.size();i++)
        MakeMap(ans[i].first,ans[i].second);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

Bob.cpp: In function 'void dfs(int, int, int, int)':
Bob.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0;j<e[i].size();j++)
      |                 ~^~~~~~~~~~~~
Bob.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for(int k=0;k<e[bg].size();k++)
      |                         ~^~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<ans.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19916 KB Output is correct
2 Correct 3 ms 19976 KB Output is correct
3 Correct 2 ms 19972 KB Output is correct
4 Correct 2 ms 17924 KB Output is correct
5 Correct 2 ms 19972 KB Output is correct
6 Correct 4 ms 19968 KB Output is correct
7 Correct 4 ms 19968 KB Output is correct
8 Correct 3 ms 19968 KB Output is correct
9 Correct 2 ms 19972 KB Output is correct
10 Correct 3 ms 17932 KB Output is correct
11 Correct 2 ms 19980 KB Output is correct
12 Correct 3 ms 19972 KB Output is correct
13 Correct 2 ms 19972 KB Output is correct
14 Correct 4 ms 19968 KB Output is correct
15 Correct 3 ms 19972 KB Output is correct
16 Correct 2 ms 19968 KB Output is correct
17 Correct 2 ms 19972 KB Output is correct
18 Correct 2 ms 19980 KB Output is correct
19 Correct 3 ms 19944 KB Output is correct
20 Correct 4 ms 19968 KB Output is correct
21 Correct 3 ms 19972 KB Output is correct
22 Correct 2 ms 19980 KB Output is correct
23 Correct 3 ms 19972 KB Output is correct
24 Correct 2 ms 17924 KB Output is correct
25 Correct 4 ms 19972 KB Output is correct
26 Correct 3 ms 20160 KB Output is correct
27 Correct 3 ms 19980 KB Output is correct
28 Correct 3 ms 19972 KB Output is correct
29 Correct 4 ms 20220 KB Output is correct
30 Correct 2 ms 17920 KB Output is correct
31 Correct 3 ms 17920 KB Output is correct
32 Correct 2 ms 17764 KB Output is correct
33 Correct 2 ms 17924 KB Output is correct
34 Correct 2 ms 17920 KB Output is correct
35 Correct 3 ms 17924 KB Output is correct
36 Correct 3 ms 19972 KB Output is correct
37 Correct 4 ms 19972 KB Output is correct
38 Correct 3 ms 19964 KB Output is correct
39 Correct 3 ms 20048 KB Output is correct
40 Correct 3 ms 19972 KB Output is correct
41 Correct 3 ms 19980 KB Output is correct
42 Correct 2 ms 19980 KB Output is correct
43 Correct 3 ms 19976 KB Output is correct
44 Correct 2 ms 17928 KB Output is correct
45 Correct 2 ms 17924 KB Output is correct
46 Correct 3 ms 20220 KB Output is correct
47 Correct 3 ms 19972 KB Output is correct
48 Correct 3 ms 20072 KB Output is correct
49 Correct 3 ms 19980 KB Output is correct
50 Correct 2 ms 17924 KB Output is correct
51 Correct 2 ms 17924 KB Output is correct
52 Correct 3 ms 19972 KB Output is correct
53 Correct 3 ms 17920 KB Output is correct
54 Correct 3 ms 19968 KB Output is correct
55 Correct 4 ms 19968 KB Output is correct
56 Correct 3 ms 19972 KB Output is correct
57 Correct 2 ms 19968 KB Output is correct
58 Correct 4 ms 19980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19916 KB Output is correct
2 Correct 3 ms 19976 KB Output is correct
3 Correct 2 ms 19972 KB Output is correct
4 Correct 2 ms 17924 KB Output is correct
5 Correct 2 ms 19972 KB Output is correct
6 Correct 4 ms 19968 KB Output is correct
7 Correct 4 ms 19968 KB Output is correct
8 Correct 3 ms 19968 KB Output is correct
9 Correct 2 ms 19972 KB Output is correct
10 Correct 3 ms 17932 KB Output is correct
11 Correct 2 ms 19980 KB Output is correct
12 Correct 3 ms 19972 KB Output is correct
13 Correct 2 ms 19972 KB Output is correct
14 Correct 4 ms 19968 KB Output is correct
15 Correct 3 ms 19972 KB Output is correct
16 Correct 2 ms 19968 KB Output is correct
17 Correct 2 ms 19972 KB Output is correct
18 Correct 2 ms 19980 KB Output is correct
19 Correct 3 ms 19944 KB Output is correct
20 Correct 4 ms 19968 KB Output is correct
21 Correct 3 ms 19972 KB Output is correct
22 Correct 2 ms 19980 KB Output is correct
23 Correct 3 ms 19972 KB Output is correct
24 Correct 2 ms 17924 KB Output is correct
25 Correct 4 ms 19972 KB Output is correct
26 Correct 3 ms 20160 KB Output is correct
27 Correct 3 ms 19980 KB Output is correct
28 Correct 3 ms 19972 KB Output is correct
29 Correct 4 ms 20220 KB Output is correct
30 Correct 2 ms 17920 KB Output is correct
31 Correct 3 ms 17920 KB Output is correct
32 Correct 2 ms 17764 KB Output is correct
33 Correct 2 ms 17924 KB Output is correct
34 Correct 2 ms 17920 KB Output is correct
35 Correct 3 ms 17924 KB Output is correct
36 Correct 3 ms 19972 KB Output is correct
37 Correct 4 ms 19972 KB Output is correct
38 Correct 3 ms 19964 KB Output is correct
39 Correct 3 ms 20048 KB Output is correct
40 Correct 3 ms 19972 KB Output is correct
41 Correct 3 ms 19980 KB Output is correct
42 Correct 2 ms 19980 KB Output is correct
43 Correct 3 ms 19976 KB Output is correct
44 Correct 2 ms 17928 KB Output is correct
45 Correct 2 ms 17924 KB Output is correct
46 Correct 3 ms 20220 KB Output is correct
47 Correct 3 ms 19972 KB Output is correct
48 Correct 3 ms 20072 KB Output is correct
49 Correct 3 ms 19980 KB Output is correct
50 Correct 2 ms 17924 KB Output is correct
51 Correct 2 ms 17924 KB Output is correct
52 Correct 3 ms 19972 KB Output is correct
53 Correct 3 ms 17920 KB Output is correct
54 Correct 3 ms 19968 KB Output is correct
55 Correct 4 ms 19968 KB Output is correct
56 Correct 3 ms 19972 KB Output is correct
57 Correct 2 ms 19968 KB Output is correct
58 Correct 4 ms 19980 KB Output is correct
59 Correct 4 ms 19972 KB Output is correct
60 Correct 4 ms 19972 KB Output is correct
61 Correct 3 ms 19972 KB Output is correct
62 Correct 4 ms 19972 KB Output is correct
63 Correct 4 ms 19972 KB Output is correct
64 Correct 4 ms 19980 KB Output is correct
65 Correct 3 ms 19964 KB Output is correct
66 Correct 4 ms 19972 KB Output is correct
67 Correct 4 ms 19972 KB Output is correct
68 Correct 4 ms 19968 KB Output is correct
69 Correct 3 ms 19972 KB Output is correct
70 Correct 3 ms 19976 KB Output is correct
71 Correct 4 ms 20232 KB Output is correct
72 Correct 3 ms 19972 KB Output is correct
73 Correct 3 ms 19972 KB Output is correct
74 Correct 4 ms 19972 KB Output is correct
75 Correct 4 ms 19972 KB Output is correct
76 Correct 4 ms 19972 KB Output is correct
77 Correct 4 ms 19972 KB Output is correct
78 Correct 4 ms 19972 KB Output is correct
79 Correct 4 ms 19976 KB Output is correct
80 Correct 3 ms 19904 KB Output is correct
81 Correct 3 ms 19972 KB Output is correct
82 Correct 3 ms 19968 KB Output is correct
83 Correct 2 ms 19980 KB Output is correct
84 Correct 4 ms 19968 KB Output is correct
85 Correct 4 ms 19972 KB Output is correct
86 Correct 2 ms 19972 KB Output is correct
87 Correct 4 ms 19972 KB Output is correct
88 Correct 3 ms 19968 KB Output is correct
89 Correct 3 ms 17920 KB Output is correct
90 Correct 3 ms 17924 KB Output is correct
91 Correct 3 ms 17924 KB Output is correct
92 Correct 3 ms 17920 KB Output is correct
93 Correct 3 ms 17920 KB Output is correct
94 Correct 4 ms 19972 KB Output is correct
95 Correct 4 ms 19972 KB Output is correct
96 Correct 4 ms 19980 KB Output is correct
97 Correct 4 ms 19972 KB Output is correct
98 Correct 3 ms 19972 KB Output is correct
99 Correct 3 ms 19972 KB Output is correct
100 Correct 3 ms 19972 KB Output is correct
101 Correct 4 ms 19980 KB Output is correct
102 Correct 3 ms 17924 KB Output is correct
103 Correct 3 ms 19972 KB Output is correct
104 Correct 3 ms 19972 KB Output is correct
105 Correct 2 ms 19968 KB Output is correct
106 Correct 4 ms 19972 KB Output is correct
107 Correct 4 ms 19972 KB Output is correct
108 Correct 2 ms 19968 KB Output is correct
109 Correct 3 ms 19972 KB Output is correct
110 Correct 2 ms 19972 KB Output is correct
111 Correct 4 ms 19968 KB Output is correct
112 Correct 4 ms 19972 KB Output is correct
113 Correct 3 ms 19980 KB Output is correct
114 Correct 4 ms 19972 KB Output is correct
115 Correct 4 ms 19972 KB Output is correct
116 Correct 3 ms 19972 KB Output is correct
117 Correct 3 ms 19980 KB Output is correct
118 Correct 3 ms 19964 KB Output is correct

Subtask #3
0 / 63.0

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