oj.uz

Submission #150907

# Submission time Handle Problem Language Result Execution time Memory
150907 2019-09-01T10:35:01 Z cheetose Senior Postmen (BOI14_postmen) C++11
55 / 100
 500 ms 84952 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int now[500005];
VPi v[500005];
bool chk[500005],instack[500005];
vector<Vi> ans;
stack<int> st;
void dfs(int N)
{
	for(int &i=now[N];i<v[N].size();i++)
	{
		if(chk[v[N][i].Y])continue;
		chk[v[N][i].Y]=1;
		dfs(v[N][i].X);
	}
	if(instack[N])
	{
		Vi v;
		while(!st.empty())
		{
			v.pb(st.top());
			instack[st.top()]=0;
			st.pop();
			if(v.back()==N)break;
		}
		ans.pb(v);
	}
	st.push(N);
	instack[N]=1;
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	fup(i,0,m-1,1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].pb(mp(y,i));
		v[y].pb(mp(x,i));
	}
	dfs(1);
	for(auto &v:ans)
	{
		for(int x:v)
			printf("%d ",x);
		puts("");
	}
	
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int &i=now[N];i<v[N].size();i++)
                    ~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
postmen.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12032 KB Output is correct
2 Correct 13 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 13 ms 12544 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 19 ms 12672 KB Output is correct
7 Correct 20 ms 14080 KB Output is correct
8 Correct 12 ms 12416 KB Output is correct
9 Correct 55 ms 24312 KB Output is correct
10 Correct 14 ms 12288 KB Output is correct
11 Correct 15 ms 12392 KB Output is correct
12 Correct 67 ms 24800 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12088 KB Output is correct
2 Correct 11 ms 12008 KB Output is correct
3 Correct 11 ms 12084 KB Output is correct
4 Correct 15 ms 12544 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 16 ms 12672 KB Output is correct
7 Correct 19 ms 14080 KB Output is correct
8 Correct 15 ms 12356 KB Output is correct
9 Correct 62 ms 24288 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 13 ms 12416 KB Output is correct
12 Correct 64 ms 24728 KB Output is correct
13 Correct 110 ms 26636 KB Output is correct
14 Correct 93 ms 21968 KB Output is correct
15 Correct 97 ms 27116 KB Output is correct
16 Correct 94 ms 26532 KB Output is correct
17 Correct 104 ms 18864 KB Output is correct
18 Correct 152 ms 24784 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12032 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 12 ms 12084 KB Output is correct
4 Correct 12 ms 12544 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 14 ms 12672 KB Output is correct
7 Correct 19 ms 14080 KB Output is correct
8 Correct 13 ms 12416 KB Output is correct
9 Correct 68 ms 24440 KB Output is correct
10 Correct 19 ms 12288 KB Output is correct
11 Correct 14 ms 12416 KB Output is correct
12 Correct 66 ms 24696 KB Output is correct
13 Correct 92 ms 26532 KB Output is correct
14 Correct 85 ms 22016 KB Output is correct
15 Correct 97 ms 27112 KB Output is correct
16 Correct 97 ms 26532 KB Output is correct
17 Correct 138 ms 18912 KB Output is correct
18 Correct 100 ms 24668 KB Output is correct
19 Execution timed out 587 ms 84952 KB Time limit exceeded
20 Halted 0 ms 0 KB -