oj.uz

답안 #429482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429482 2021-06-16T03:30:40 Z inwbear Simurgh (IOI17_simurgh) C++14
30 / 100
 236 ms 2248 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
bool uu[125255];
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;
            nw=count_common_roads(ans);
            if(nw>tp)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;
            nw=count_common_roads(ans);
            if(nw>tp)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;
            nw=count_common_roads(ans);
            if(nw>tp)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:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 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 1 ms 312 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

# 결과 실행 시간 메모리 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 1 ms 312 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 12 ms 332 KB correct
15 Correct 9 ms 340 KB correct
16 Correct 8 ms 336 KB correct
17 Correct 11 ms 336 KB correct
18 Correct 4 ms 204 KB correct
19 Correct 11 ms 332 KB correct
20 Correct 9 ms 332 KB correct
21 Correct 8 ms 332 KB correct
22 Correct 6 ms 308 KB correct
23 Correct 6 ms 324 KB correct
24 Correct 6 ms 320 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 456 KB correct
31 Correct 8 ms 308 KB correct
32 Correct 8 ms 204 KB correct
33 Correct 7 ms 204 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 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 1 ms 312 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 12 ms 332 KB correct
15 Correct 9 ms 340 KB correct
16 Correct 8 ms 336 KB correct
17 Correct 11 ms 336 KB correct
18 Correct 4 ms 204 KB correct
19 Correct 11 ms 332 KB correct
20 Correct 9 ms 332 KB correct
21 Correct 8 ms 332 KB correct
22 Correct 6 ms 308 KB correct
23 Correct 6 ms 324 KB correct
24 Correct 6 ms 320 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 456 KB correct
31 Correct 8 ms 308 KB correct
32 Correct 8 ms 204 KB correct
33 Correct 7 ms 204 KB correct
34 Incorrect 236 ms 1100 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 160 ms 2248 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 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 1 ms 312 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 12 ms 332 KB correct
15 Correct 9 ms 340 KB correct
16 Correct 8 ms 336 KB correct
17 Correct 11 ms 336 KB correct
18 Correct 4 ms 204 KB correct
19 Correct 11 ms 332 KB correct
20 Correct 9 ms 332 KB correct
21 Correct 8 ms 332 KB correct
22 Correct 6 ms 308 KB correct
23 Correct 6 ms 324 KB correct
24 Correct 6 ms 320 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 456 KB correct
31 Correct 8 ms 308 KB correct
32 Correct 8 ms 204 KB correct
33 Correct 7 ms 204 KB correct
34 Incorrect 236 ms 1100 KB WA in grader: NO
35 Halted 0 ms 0 KB -