oj.uz

Submission #429603

# Submission time Handle Problem Language Result Execution time Memory
429603 2021-06-16T07:40:38 Z inwbear Simurgh (IOI17_simurgh) C++14
30 / 100
 192 ms 1680 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
bool uu[125255],cc[505];
int h[505],bs[505],par[505],tp,a,b,cur,tpans,nw;
vector<int>vv[505];
int F(int N)
{
    if(bs[N]==N)return N;
    else return bs[N]=F(bs[N]);
}
void un(int X,int Y)
{
    bs[F(X)]=F(Y);
    return;
}
void dfs(int N,int pr,int H)
{
    par[N]=pr;
    h[N]=H;
    for(int i=0;i<vv[N].size();i++)
    {
        if(vv[N][i]==pr)continue;
        dfs(vv[N][i],N,H+1);
    }
    return;
}
vector<int> find_roads(int n,vector<int>u,vector<int>v)
{
    vector<int>ryl;
	vector<int>ans;
    for(int i=0;i<n;i++)bs[i]=i;
    for(int i=0;i<u.size();i++)
    {
        uu[i]=false;
       // printf("%d %d\n",F(u[i]),F(v[i]));
        if(F(u[i])==F(v[i]))continue;
        un(u[i],v[i]);
       // printf("[%d]",i);
        ans.pb(i);
        ryl.pb(0);
        uu[i]=true;
    }
    tp=count_common_roads(ans);
    for(int i=0;i<u.size();i++)
    {
        if(uu[i])continue;
        a=u[i],b=v[i];
        for(int i=0;i<n;i++)vv[i].clear();
        for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
        dfs(1,-1,1);
		//for(int i=0;i<n;i++)printf("%d %d %d\n",par[i],h[i],i);
        if(h[a]<h[b])swap(a,b);
        while(h[a]>h[b])
        {
            for(int i=0;i<ans.size();i++)
            {
                if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
            }
            a=par[a];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            continue;
        }
        while(a!=b)
        {
            for(int i=0;i<ans.size();i++)
            {
                if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
            }
            a=par[a];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
            for(int i=0;i<ans.size();i++)
            {
                if((b==u[ans[i]]&&par[b]==v[ans[i]])||(par[b]==u[ans[i]]&&b==v[ans[i]]))cur=i;
            }
            b=par[b];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            continue;
        }
    }
	return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<vv[N].size();i++)
      |                 ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
      |                     ~^~~~~~~~~~~
simurgh.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 8 ms 332 KB correct
15 Correct 5 ms 332 KB correct
16 Correct 7 ms 332 KB correct
17 Correct 6 ms 204 KB correct
18 Correct 3 ms 204 KB correct
19 Correct 7 ms 332 KB correct
20 Correct 6 ms 332 KB correct
21 Correct 7 ms 324 KB correct
22 Correct 5 ms 324 KB correct
23 Correct 5 ms 328 KB correct
24 Correct 6 ms 324 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 5 ms 204 KB correct
27 Correct 6 ms 204 KB correct
28 Correct 2 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 7 ms 204 KB correct
31 Correct 10 ms 320 KB correct
32 Correct 8 ms 320 KB correct
33 Correct 7 ms 324 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 8 ms 332 KB correct
15 Correct 5 ms 332 KB correct
16 Correct 7 ms 332 KB correct
17 Correct 6 ms 204 KB correct
18 Correct 3 ms 204 KB correct
19 Correct 7 ms 332 KB correct
20 Correct 6 ms 332 KB correct
21 Correct 7 ms 324 KB correct
22 Correct 5 ms 324 KB correct
23 Correct 5 ms 328 KB correct
24 Correct 6 ms 324 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 5 ms 204 KB correct
27 Correct 6 ms 204 KB correct
28 Correct 2 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 7 ms 204 KB correct
31 Correct 10 ms 320 KB correct
32 Correct 8 ms 320 KB correct
33 Correct 7 ms 324 KB correct
34 Incorrect 192 ms 784 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 179 ms 1680 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 8 ms 332 KB correct
15 Correct 5 ms 332 KB correct
16 Correct 7 ms 332 KB correct
17 Correct 6 ms 204 KB correct
18 Correct 3 ms 204 KB correct
19 Correct 7 ms 332 KB correct
20 Correct 6 ms 332 KB correct
21 Correct 7 ms 324 KB correct
22 Correct 5 ms 324 KB correct
23 Correct 5 ms 328 KB correct
24 Correct 6 ms 324 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 5 ms 204 KB correct
27 Correct 6 ms 204 KB correct
28 Correct 2 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 7 ms 204 KB correct
31 Correct 10 ms 320 KB correct
32 Correct 8 ms 320 KB correct
33 Correct 7 ms 324 KB correct
34 Incorrect 192 ms 784 KB WA in grader: NO
35 Halted 0 ms 0 KB -