oj.uz

답안 #359245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359245 2021-01-26T13:30:49 Z beksultan04 Simurgh (IOI17_simurgh) C++14
0 / 100
 1 ms 364 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;
            pos[y]=1;
            vector <int> ask;
            for (i=0;i<u.size();++i)
                if (a[i] == 1)ask.pb(i);
            if (ask.size() != n-1)assert(0);
            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){
                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:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for (i=0;i<u.size();++i)
      |                      ~^~~~~~~~~
simurgh.cpp:103:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |             if (ask.size() != n-1)assert(0);
      |                 ~~~~~~~~~~~^~~~~~
simurgh.cpp:110: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]
  110 |         for (i=0;i<ans.size();++i){
      |                  ~^~~~~~~~~~~
simurgh.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (i =0;i<otvet.size();++i){
      |               ~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB WA in grader: NO
2 Halted 0 ms 0 KB -