oj.uz

Submission #265346

# Submission time Handle Problem Language Result Execution time Memory
265346 2020-08-14T16:14:14 Z arayi Simurgh (IOI17_simurgh) C++17
0 / 100
 149 ms 16120 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
#define ask count_common_roads
using namespace std;

const int N = 500 * 500 + 500;

int col[N], ind[N];
vector <pair <int, int> > g[N];
vector <int> sm;
vector <int> a[N], fp;
bool cl[N];
void dfs(int v)
{
    a[v] = fp;
    cl[v] = true;
    for(auto p : g[v])
    {
        if(cl[p.fr]) continue;
        ind[p.sc] = sm.size();
        sm.ad(p.sc);
        fp.ad(p.sc);
        dfs(p.fr);
        fp.pop_back();
    }
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	for (int i = 0; i < u.size(); i++)
	{
	    g[u[i]].ad(MP(v[i], i));
	    g[v[i]].ad(MP(u[i], i));
	}
	dfs(0);
	//for(auto p : sm) cout << p << " ";
	//cout << endl;
	int ss = ask(sm);
	for (int i = 0; i < u.size(); i++)
	{
	    if((int)a[u[i]].size() <= (int)a[v[i]].size() + 1) swap(u[i], v[i]);
	    if((int)a[u[i]].size() <= (int)a[v[i]].size() + 1) continue;
	    //cout << i << endl;
	    vector <int> b;
	    for (int j = (int)a[v[i]].size(); j < (int)a[u[i]].size(); j++)
	        b.ad(a[u[i]][j]);
        bool bl = false;
        for(auto p : b)
        {
            if(col[p] == -1)
            {
                sm[ind[p]] = i;
                if(ask(sm) == ss) col[i] = -1;
                else col[i] = 1;
                sm[ind[p]] = p;
                bl = true;
                break;
            }
            else if(col[p] == 1)
            {
                sm[ind[p]] = i;
                if(ask(sm) == ss) col[i] = 1;
                else col[i] = -1;
                sm[ind[p]] = p;
                bl = true;
                break;
            }
        }
        if(bl)
        {
            for(auto p : b)
            {
                if(col[p] == 0)
                {
                    sm[ind[p]] = i;
                    if(ask(sm) == ss) col[p] = col[i];
                    else col[p] = 0 - col[i];
                    sm[ind[p]] = p;
                }
            }
            continue;
        }
        vector <pair<int, int> > c;
        c.ad(MP(ss, i));
        for(auto p : b)
        {
            sm[ind[p]] = i;
            int i1 = ask(sm);
            c.ad(MP(i1, p));
            sm[ind[p]] = p;
        }
        sort(c.begin(), c.end());
        for(auto p : c)
        {
            if(c[0].fr == p.fr) col[p.sc] = 1;
            else col[p.sc] = -1;
        }
	}
	vector <int> pat;
	for (int i = 0; i < u.size(); i++)
	{
	    if(col[i] >= 0) pat.ad(i);
	}
	return pat;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~
simurgh.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~
simurgh.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB correct
2 Correct 8 ms 12160 KB correct
3 Correct 9 ms 12160 KB correct
4 Correct 9 ms 12160 KB correct
5 Correct 10 ms 12032 KB correct
6 Incorrect 9 ms 12160 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB correct
2 Correct 8 ms 12160 KB correct
3 Correct 9 ms 12160 KB correct
4 Correct 9 ms 12160 KB correct
5 Correct 10 ms 12032 KB correct
6 Incorrect 9 ms 12160 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB correct
2 Correct 8 ms 12160 KB correct
3 Correct 9 ms 12160 KB correct
4 Correct 9 ms 12160 KB correct
5 Correct 10 ms 12032 KB correct
6 Incorrect 9 ms 12160 KB WA in grader: NO
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12032 KB correct
2 Correct 9 ms 12160 KB correct
3 Incorrect 149 ms 16120 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB correct
2 Correct 8 ms 12160 KB correct
3 Correct 9 ms 12160 KB correct
4 Correct 9 ms 12160 KB correct
5 Correct 10 ms 12032 KB correct
6 Incorrect 9 ms 12160 KB WA in grader: NO
7 Halted 0 ms 0 KB -