oj.uz

Submission #359240

# Submission time Handle Problem Language Result Execution time Memory
359240 2021-01-26T13:19:53 Z beksultan04 Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 5724 KB 
#include "simurgh.h"
#ifndef EVAL
#include "grader.cpp"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
vector <pii> g[501];
vector <int> which,cycle,top,otvet;
bool vis[501],can[1000001],used[1000001],pos[1000001];
int kto[501][501];
void dfs(int x){
    vis[x] = 1;
    for (pii to: g[x])
        if (vis[to.fr] == 0){
            which.pb(to.sc);
            dfs(to.fr);
        }
}

void find_cycle(int x,int pr = -1){
    top.pb(x);
    vis[x]=1;
    for (pii to: g[x]){
        if (to.fr != pr && can[to.sc] == 1){
            if (vis[to.fr] == 1){
                int pr = to.fr;
                while (!top.empty()){
                    cycle.pb(kto[top.back()][pr]);
                    pr = top.back();
                    if (top.back() == to.fr)break;
                    top.pop_back();
                }
                ret;
            }
            if (!cycle.empty())ret;
            if (vis[to.fr] == 0){
                find_cycle(to.fr,x);
            }
        }
            if (!cycle.empty())ret;
    }
            if (!cycle.empty())ret;
    top.pop_back();
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<int> bosh,a;
	int i;
	for (i=0;i<u.size();++i){
        g[u[i]].pb({v[i],i});
	    g[v[i]].pb({u[i],i});
	    kto[u[i]][v[i]] = i;
	    kto[v[i]][u[i]] = i;
        a.pb(0);
        otvet.pb(-1);
	}
	dfs(0);
	for (int x : which){
        used[x] = 1;
        can[x] = 1;
        a[x] = 1;
        otvet[x]=1;
	}

	for (i=0;i<u.size();++i)
        if (!used[i])
            bosh.pb(i);
    for (int x: bosh){
        for (i=0;i<n;++i)vis[i] = 0;
        can[x] = 1;
        a[x] = 1;
        cycle.clear();
        top.clear();
        vector <pii> ans;
        find_cycle(0);
        for (int y: cycle){
            if (pos[y] == 1)continue;
            a[y]=0;
            vector <int> ask;
            for (i=0;i<u.size();++i)
                if (a[i] == 1)ask.pb(i);
            ans.pb({count_common_roads(ask),y});
            a[y]=1;
        }
        sort(all(ans));
        if (ans.empty())continue;
        int mn = ans.back().fr;
        for (i=0;i<ans.size();++i){
            if (mn > ans[i].fr){
            pos[ans[i].sc] = 1;
                otvet[ans[i].sc]=1;
            }
            else
                otvet[ans[i].sc]=0;
        }
        can[x]=0;
        a[x]=0;
    }
    vector <int> res;
    for (i =0;i<otvet.size();++i){
        if (otvet[i] == 1){
            res.pb(i);
        }
    }
    ret res;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (i=0;i<u.size();++i){
      |           ~^~~~~~~~~
simurgh.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (i=0;i<u.size();++i)
      |           ~^~~~~~~~~
simurgh.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (i=0;i<u.size();++i)
      |                      ~^~~~~~~~~
simurgh.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (i=0;i<ans.size();++i){
      |                  ~^~~~~~~~~~~
simurgh.cpp:120:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (i =0;i<otvet.size();++i){
      |               ~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 0 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 512 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 116 ms 596 KB correct
15 Correct 114 ms 492 KB correct
16 Correct 120 ms 492 KB correct
17 Correct 77 ms 576 KB correct
18 Correct 15 ms 492 KB correct
19 Correct 79 ms 492 KB correct
20 Correct 72 ms 492 KB correct
21 Correct 65 ms 492 KB correct
22 Correct 14 ms 492 KB correct
23 Correct 12 ms 492 KB correct
24 Correct 9 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 10 ms 492 KB correct
27 Correct 11 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 13 ms 492 KB correct
31 Correct 14 ms 492 KB correct
32 Correct 13 ms 492 KB correct
33 Correct 13 ms 492 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 0 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 512 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 116 ms 596 KB correct
15 Correct 114 ms 492 KB correct
16 Correct 120 ms 492 KB correct
17 Correct 77 ms 576 KB correct
18 Correct 15 ms 492 KB correct
19 Correct 79 ms 492 KB correct
20 Correct 72 ms 492 KB correct
21 Correct 65 ms 492 KB correct
22 Correct 14 ms 492 KB correct
23 Correct 12 ms 492 KB correct
24 Correct 9 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 10 ms 492 KB correct
27 Correct 11 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 13 ms 492 KB correct
31 Correct 14 ms 492 KB correct
32 Correct 13 ms 492 KB correct
33 Correct 13 ms 492 KB correct
34 Incorrect 2821 ms 2540 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 364 KB correct
2 Correct 1 ms 364 KB correct
3 Execution timed out 3066 ms 5724 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 0 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 512 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 116 ms 596 KB correct
15 Correct 114 ms 492 KB correct
16 Correct 120 ms 492 KB correct
17 Correct 77 ms 576 KB correct
18 Correct 15 ms 492 KB correct
19 Correct 79 ms 492 KB correct
20 Correct 72 ms 492 KB correct
21 Correct 65 ms 492 KB correct
22 Correct 14 ms 492 KB correct
23 Correct 12 ms 492 KB correct
24 Correct 9 ms 492 KB correct
25 Correct 1 ms 492 KB correct
26 Correct 10 ms 492 KB correct
27 Correct 11 ms 492 KB correct
28 Correct 3 ms 492 KB correct
29 Correct 1 ms 492 KB correct
30 Correct 13 ms 492 KB correct
31 Correct 14 ms 492 KB correct
32 Correct 13 ms 492 KB correct
33 Correct 13 ms 492 KB correct
34 Incorrect 2821 ms 2540 KB WA in grader: NO
35 Halted 0 ms 0 KB -